ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

MSU SE and Ural SU contest. Petrozavodsk training camp. Summer 2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Game with Cards

Time limit: 0.5 second
Memory limit: 64 MB
Tyomitch plays the following game with N of his friends. Tyomitch leaves the room. His friends write numbers from 1 to N on cards, and each of the friends takes a card in a way that Tyomitch doesn't know which card each one has. Let's number the friends from 1 to N. After Tyomitch comes back to the room, each of his friends makes 2 statements of the following form (examples given for i'th friend):
  1. I have the card number ai.
  2. bi'th friend has the card number ci (bii).
Exactly one of these statements is true, and the other one is false. It's known that no two friends said that friend b has card c, and nobody said that friend b has card c if b admitted that he has this very card. The task for Tyomitch is to determine for each of his friends which of his statements is true.

Input

The first line of the input contains the number N (2 ≤ N ≤ 1000). Each of the following N lines contains a triple ai, bi, ci — the statements of Tyomitch's friends.

Output

The only line of output must contain N numbers separated with spaces, being the numbers of the true statement (either 1 or 2) for each of the friends. It is known that a solution exists.

Sample

inputoutput
5
3 4 3
1 3 2
3 2 5
2 5 4
3 4 1
1 2 2 2 2
Problem Author: Alexander Ipatov, special thanks to Dmitry Ivankov
Problem Source: Petrozavodsk summer training camp, August 2005.
To submit the solution for this problem go to the Problem set: 1382. Game with Cards