404238: GYM101466 C Planet Communcation

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Planet Communcationtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Lately the communication between planets has been an important issue, which is why the Earth has made many efforts to be connected to every other planet in the universe.

The Universal Network Army of Lasers (UNAL) is trying to connect the Earth with other planets in the universe. In order to make this, the UNAL uses a laser machine which each time it is used, it sends a communication signal in the form of a ray of light in the direction of the planet.

This laser machine is so powerful, that a ray of light generated by it is capable to cross all the planets it touches until the end of the universe. Moreover, when it fires a ray of light in one direction it also fires a ray of light in the opposite direction.

Given the coordinates of all the planets in the universe, help the UNAL to design the way to communicate the Earth with all other planets in the universe using the machine the minimum number of times.

Input

The first line of input contains one integer n (1 ≤ n ≤ 5000), the number of planets.

The next n lines contains the list of coordinates of the planets. In particular, the i - th line contains three integers xi, yi, zi ( - 109 ≤ xi, yi, zi ≤ 109), the coordinates of the i - th planet, respectively. The Earth is the first planet on the list. It is guaranteed that all the planets have different coordinates.

Output

Output a single integer, the minimun number of times the machine should be used to communicate the Earth with all other planets in the universe

ExamplesInput
3
0 0 0
1 1 0
-1 -1 0
Output
1
Input
4
0 0 0
1 0 0
0 1 0
0 0 1
Output
3

加入题单

上一题 下一题 算法标签: