#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
unordered_map<int, vector<int>> G;
// Input edges
for (int i = 0; i < n ; i++) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
}
// Queue and visited array
queue<int> q;
vector<bool> visited(n + 1, false);
// count array
vector<int> cnt(n+1, 0);
// Insert root (1)
q.push(1);
visited[1] = true;
// BFS traversal
while (!q.empty()) {
int front = q.front();
q.pop();
int count = 0;
cout << front << " ";
for (int child : G[front]) {
if (!visited[child]) {
visited[child] = true;
q.push(child);
count++;
}
}
cnt[front] = count;
}
cout<<endl;
for(int i=1; i<=n+1; i++){
cout<<"children of "<< i<< ": " << cnt[i] << "\n";
}
cout<<"leaf nodes \n";
for(int i=1; i<=n+1; i++){
if(cnt[i]==0){
cout<< i<<" ";
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewogICAgaW50IG47CiAgICBjaW4gPj4gbjsKCiAgICB1bm9yZGVyZWRfbWFwPGludCwgdmVjdG9yPGludD4+IEc7CgogICAgLy8gSW5wdXQgZWRnZXMKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbiA7IGkrKykgewogICAgICAgIGludCBhLCBiOwogICAgICAgIGNpbiA+PiBhID4+IGI7CgogICAgICAgIEdbYV0ucHVzaF9iYWNrKGIpOwogICAgfQoKICAgIC8vIFF1ZXVlIGFuZCB2aXNpdGVkIGFycmF5CiAgICBxdWV1ZTxpbnQ+IHE7CiAgICB2ZWN0b3I8Ym9vbD4gdmlzaXRlZChuICsgMSwgZmFsc2UpOwogICAgCiAgICAvLyBjb3VudCBhcnJheQogICAgdmVjdG9yPGludD4gY250KG4rMSwgMCk7CgogICAgLy8gSW5zZXJ0IHJvb3QgKDEpCiAgICBxLnB1c2goMSk7CiAgICB2aXNpdGVkWzFdID0gdHJ1ZTsKCiAgICAvLyBCRlMgdHJhdmVyc2FsCiAgICB3aGlsZSAoIXEuZW1wdHkoKSkgewogICAgICAgIGludCBmcm9udCA9IHEuZnJvbnQoKTsKICAgICAgICBxLnBvcCgpOwogICAgICAgIAogICAgICAgIGludCBjb3VudCA9IDA7CgogICAgICAgIGNvdXQgPDwgZnJvbnQgPDwgIiAiOwoKICAgICAgICBmb3IgKGludCBjaGlsZCA6IEdbZnJvbnRdKSB7CiAgICAgICAgICAgIGlmICghdmlzaXRlZFtjaGlsZF0pIHsKICAgICAgICAgICAgICAgIHZpc2l0ZWRbY2hpbGRdID0gdHJ1ZTsKICAgICAgICAgICAgICAgIHEucHVzaChjaGlsZCk7CiAgICAgICAgICAgICAgICBjb3VudCsrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIGNudFtmcm9udF0gPSBjb3VudDsKICAgIH0KICAgIAogICAgCiAgICBjb3V0PDxlbmRsOwogICAgCiAgICBmb3IoaW50IGk9MTsgaTw9bisxOyBpKyspewogICAgCWNvdXQ8PCJjaGlsZHJlbiBvZiAiPDwgaTw8ICI6ICIgPDwgY250W2ldIDw8ICJcbiI7CiAgICAJCiAgICB9CiAgICAKICAgIGNvdXQ8PCJsZWFmIG5vZGVzIFxuIjsKICAgIAogICAgZm9yKGludCBpPTE7IGk8PW4rMTsgaSsrKXsKICAgIAlpZihjbnRbaV09PTApewogICAgCQljb3V0PDwgaTw8IiAiOwogICAgCX0KICAgIH0KCiAgICByZXR1cm4gMDsKfQ==