Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

WROTATIO - Wheel Rotation

Fatih Gelgi, 2008
Points: 70

Farmer John has an old-time thresher (wheat harvester) that requires belts to be installed on various gears to turn the parts. The engine drives pulley 1 in a clockwise direction which attaches via a belt to pulley 2. Pulley 2 attaches via a belt to pulley 3 and so on through a total of N (2 <= N <= 1,000) pulleys (and N-1 belts).

The diagram above depicts the two ways a belt can be installed between two gears. In this illustration, pulley 1's belt directly drives pulley 2 (a 'straight' connection) and thus they will rotate in the same direction. Pulley 3 drives pulley 4 via a 'crossed belt' that reverses the direction of the rotation.

Given a list of the belt types that connect the pulleys along with the fact that pulley 1 is driven in a clockwise direction by the engine, determine the drive direction of pulley N. Each belt is described by three integers: * 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

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

Output

  • Line 1: A single integer that is the rotation direction for pulley N (0=clockwise, 1=counterclockwise)

Example

Input:
4
2 3 0
3 4 1
1 2 0

Output:
1

Input details

As in the example illustration.


Adicionado por:Wanderley Guimarăes
Data:2008-10-24
Tempo limite:0.200s-0.400s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM qobi SCM guile ST TEXT WHITESPACE
Origem:USACO October 2008 Qualifying Round

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.