# IOICJ 92 Double path tree ( Ad hoc, Timestamp )

Problem Description:
Given a tree, you want to do the least amount of operations to assert that for any two distinct nodes, there are at least two distinct simple paths that connect them.

Constraints:
1≤T≤300
3≤n≤1e5
1≤xi,yi≤n
A valid tree is given
Input file is less than 10 MB

Sample Input:
2
3
1 2
2 3
5
1 2
1 3
2 4
2 5

Sample Output:
1
1 3
2
4 5
4 3

Solution:
Consider extending the tree out so that no edges intersect. Imagine that all the leaves form somewhat a circle. Join every leaf with the leaf that is half the number of leaves away clockwise.

```const int MAXN = ( int ) 1e5;

int N;
vvi G;
int ROOT;

void init(){
cin >> N;
G = vvi( N );
for( int i = 0; i < N - 1; ++i ){
int u, v; cin >> u >> v; --u, --v;
G[ u ].emplace_back( v );
G[ v ].emplace_back( u );
}
for( int i = 0; i < N; ++i ){
if( G[ i ].size() > 1 ){
ROOT = i;
break;
}
}
}

int TS;
int tin[ MAXN ];

void build_ts( int u, int fa ){
tin[ u ] = ++TS;
for( int v : G[ u ] ){
if( v == fa ) continue;
build_ts( v, u );
}
}

void preprocess(){
TS = 0;
build_ts( ROOT, -1 );
}

bool cmp( int a, int b ){
return tin[ a ] < tin[ b ];
}

void solve(){
vi leaf;
for( int i = 0; i < N; ++i ){
if( G[ i ].size() > 1 ) continue;
leaf.emplace_back( i );
}
sort( leaf.begin(), leaf.end(), cmp );
cout << ( leaf.size() + 1 ) / 2 << endl;
for( int i = 0; i < leaf.size() / 2; ++i ){
cout << leaf[ i ] + 1 << " " << leaf[ leaf.size() / 2 + i ] + 1 << endl;
}
if( leaf.size() & 1 ){
cout << leaf.back() + 1 << " " << leaf[ leaf.size() / 2 ] + 1 << endl;
}
}
```