GSHS에 다니는 건우는 국어 시간에 성씨에 대한 수업을 받았다.  수업을 한 윤선생님은 학생들에게 과제를 나누어 주었다.

과제의 내용은 자신의 성(family name)에 대한 시조(root)를 찾아오는 과제를 제시하였다.

건우의 조상들은 특이하게 자식들을 최대 2명만 키운 역사를 가지고 있다. 쉽게 이야기해서 자식이 3명인 경우는 없다.

그리고 조상들은 자식을 낳으면 왼쪽이나 오른쪽에 구분하여 위치시키고 이를 구분하여 표시하였다.

건우의 시조를 찾아보자.

입력으로 서열에 해당하는 번호를 주고, 건우의 조상들에 대한 부모 - 자식관계가 입력으로 들어온다.

첫줄에 건우의 번호 : K  (1<= K <=1,000,000인 정수)

둘째줄에는 부모-자식관계의 수: N ( 0<= N <= 100인 정수)

셋째줄부터 N개의 관계가 주어진다.- 이때 부모 - 왼쪽자식-오른쪽자식순으로 입력된다.(단 없는 자식은 0으로 입력된다.)

예를 들면  건우의 조상들이 있으면 건우가 1이면

입력은

1

2

3 2 4

5 3 1

출력은

5