Description

Farmer John has an old-time thresher that uses belts on pulleys to transmit motion. The engine drives pulley 1 in a clockwise direction. Pulley 1 is connected to pulley 2 by a belt, pulley 2 to pulley 3, and so on, for a total of $N$ pulleys ($2 \le N \le 1000$) and $N - 1$ belts.

There are two ways to install a belt between two pulleys:

• Straight connection: the two pulleys rotate in the same direction.
• Crossed connection: the two pulleys rotate in opposite directions.

You are given a list of all belts. Each belt is specified by three integers:

• $S_i$: the driving (source) pulley.
• $D_i$: the driven (destination) pulley.
• $C_i$: the connection type ($0$ = straight, $1$ = crossed).

The belts are listed in random order. Knowing that pulley 1 rotates clockwise, determine the rotation direction of pulley $N$.

* S_i -- the driving (source) pulley 
* D_i -- the driven (destination) pulley 
* C_i -- the connection type (0=straight, 1=crossed) 
Unfortunately, FJ lists the belts in random order. 
By way of example, consider the illustration below. N = 4, and pulley 1 is driven clockwise by the thresher engine. Straight 
belts drive pulley 2 and then pulley 3, so they rotate clockwise. The crosswise belt reverses the rotation direction so pulley 4 (pulley N) rotates counterclockwise. 

Input Format

• Line 1: A single integer $N$.
• Lines 2 to $N$: Each line describes a belt with three integers $S_i$, $D_i$, and $C_i$.

Output Format

• Line 1: A single integer indicating the rotation direction of pulley $N$ ($0$ = clockwise, $1$ = counterclockwise).

4 
2 3 0 
3 4 1 
1 2 0 

1 

Hint

As in the example illustration.

Translated by ChatGPT 5