#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> edge_list(n+m+1);
vector<bool> isLeaf(n+m+1, false);
set<int> s;
for (int i = 0; i < n+m-1; i ++) {
int u, v;
cin >> u >> v;
edge_list[u].pb(v);
edge_list[v].pb(u);
if (u <= n) {isLeaf[u] = true; s.insert(v);}
if (v <= n) {isLeaf[v] = true; s.insert(u);}
}
vector<int> ans;
set<int> list_of_ans;
map<int, int> cnt;
int max_ans = 0;
while (!s.empty()) {
vector<int> parent_of_leaf;
for (auto i : s) {parent_of_leaf.pb(i);}
s.clear();
for (int i = 0; i < parent_of_leaf.size(); i ++) {
if (isLeaf[parent_of_leaf[i]]) {continue;}
vector<int> notLeaf;
for (auto j : edge_list[parent_of_leaf[i]]) {
if (!isLeaf[j]) {notLeaf.pb(j);}
}
if (notLeaf.size() == 1) {
isLeaf[parent_of_leaf[i]] = true;
int new_ans = edge_list[parent_of_leaf[i]].size()-1;
max_ans = max(max_ans, new_ans);
cnt[new_ans] ++;
s.insert(notLeaf[0]);
}
else if (notLeaf.size() == 0) {
isLeaf[parent_of_leaf[i]] = true;
int new_ans = edge_list[parent_of_leaf[i]].size()-1; // -1 is because of the "round table permutation problem"
max_ans = max(max_ans, new_ans);
cnt[new_ans] ++;
}
}
}
int ans_cnt = 0;
for (int i = max_ans; i > 1; i --) {
ans_cnt += cnt[i];
cout << i << " " << ans_cnt << endl;
}
}
