10
1 2
1 3
3 4
3 5
3 6
4 7
4 8
8 9
8 10
0 1 0 1 0 1 0 1 0 1
9
2 1 1
2 4 4
2 3 0
1 1 2
2 3 4
1 4 1
2 1 1
2 4 4
2 3 2

1
3
0
6
3
4
6