4
2 4 3
2 4 4
2 1 1
2 3 4
// 2 1 2 2


4
3 2 1
2 1 1
4 4 4
2 3 1
// 1 1 2 2

2
2 2 2
1 1 1
// 1 1


3
1 2 1
2 3 2
3 1 3
// 1 1 1

Edited by author 24.01.2009 20:24

Hint:
Try to build bipartite graph with 2*N edges. Then iteratively find vertice with only one connected edge. This edge will be "true" anyhow, so its pair from the guy's statement is "false". Also "false" are all edges, connected to both vertices of current one, and then you can mark their pairs as "true" ans so on...

What residue graph after this procedure.
Can it have vertices with deg>2?
Logically it must be union of separeted edges(matched vertices) and disjoint circles. But My Ac prog
says that in 9 test residue graph has vertice with deg>2.

Edited by author 20.06.2009 09:17

I'm not sure how do you build that "residue graph", but the answer is most likely to be "no"))
I would not mind helping you, but don't want to post ideas in forum.

Edited by author 19.06.2009 13:37

5
5 4 5
5 1 5
4 1 5
4 4 3
4 1 5

5
2 5 4
4 5 1
3 4 3
3 5 5
1 5 5

I hope they can help~
o(∩_∩)o...

Both of these tests are incorrect. My AC program fails on them.

input:
6
1 2 4
2 3 5
3 1 6
1 5 4
5 6 5
6 4 6

output:
1 1 1 2 2 2

hope can help you.
GOOD LUCK!!!

Thank U but they're weak

What if there is no such edge?