Problem:


Amida, the City of Miracle

奇跡の都市アミダ（Amida, the City of Miracle）の市長は他の市のように選挙で選ぶのではない．かつて長い政権闘争と天変地異により疲弊したこの都市は，候補者全員を公平に選び，かつ幸運の星の下に生まれた者を市長にするために，候補者全員の運命をくじにゆだねることにしたのである．後にあみだくじと呼ばれるくじである．

選挙は以下のように行われる．候補者数と同数の長い縦線が引かれ，さらにいくつかの横線がそこに引かれる．横線は隣接した縦線の途中同士を結ぶように引かれる．いずれかの縦線の下には「当選」と書かれている．どの縦線が当選であるかは候補者からわからないように隠される．それぞれの候補者は縦線を 1 つ選択する．全ての候補者の選択が終わると，各候補者は線を上から下に向かってたどる．ただし，移動途中に横線が見つかったときは，横線の接続された反対側の縦線に移り，また下に向かってたどる．縦線の一番下までたどり着いたときに，そこに「当選」と書かれていた者が当選して，次期市長となる．

この方法はうまくいった．幸運な市長の下に，争いも災害も少ない平和な時代が続いた．しかし近年，人口増加のためにこの手法に限界が見えてきた．候補者が増えたため，あみだくじが大規模になり，手作業による集計では非常に時間がかかるようになったのである．そこで市では，市役所のプログラマーであるあなたにあみだくじの電算化を依頼した．

あなたの仕事は，あみだくじの構造と，選択された縦線の位置が与えられたときに，最終的にどの縦線にたどり着くかを求めるプログラムを書くことである．

以下の図は，サンプルとして与えた入力および出力の内容を示したものである．

Input

入力は複数のデータセットからなる．1 つのデータセットは以下のように与えられる．

n m a

横線1

横線2

横線3

...

横線m

n ，m ，a はそれぞれ 2 <= n <= 100, 0 <= m <= 1000, 1 <= a <= n をみたす整数であり，それぞれ縦線の本数，横線の本数，調べる縦線の番号を表す．

横線のデータは以下のように与えられる．

h p q

h ，p ，q はそれぞれ 1 <= h <= 1000, 1 <= p < q <= n, を満たす整数であり，h はその横線の高さ，p ，q はその横線につながっている 2 本の縦線の番号を表す．

1 つの縦線の同じ高さに，異なる横線が 2 つ以上つくことはない．

入力の終わりには，空白で区切られた 3 つのゼロのみからなる行がある。

Output

それぞれのデータセットに対して 1 行ずつ，縦線 a の上端からたどったときの下端における縦線の番号を出力しなさい．

Sample Input

4 4 1
3 1 2
2 2 3
3 3 4
1 3 4
0 0 0

Output for the Sample Input

4



Sample input:
4 4 1
3 1 2
2 2 3
3 3 4
1 3 4
0 0 0


Sample output:
4

Submission status: Accepted

Solution code:
while True:
    n,m,a=map(int,raw_input().split())
    if n==m==a==0:break
    L=range(n+1)
    data=[map(int,raw_input().split()) for i in range(m)]
    data.sort()
    for i,j,k in data:
        L[j],L[k]=L[k],L[j]
    print L[a]

Submission status: Accepted

Solution code:
while 1:
        num=map(int,raw_input().split())
        if num==[0,0,0] : break
        hrz=[0 for i in range(num[1])]
        for i in range(num[1]):
                hrz[i]=map(int,raw_input().split())
        pps=[1001,num[2]]
        while pps!=[0,0]:
                lct,pps=pps,[0,0]
                for i in range(num[1]):
                        if pps[0]<hrz[i][0]<lct[0]:
                                if hrz[i][1]==lct[1]:
                                        pps=[hrz[i][0],hrz[i][2]]
                                elif hrz[i][2]==lct[1]:
                                        pps=[hrz[i][0],hrz[i][1]]
        print lct[1]

Submission status: Accepted

Solution code:
while True:
    n, m, a = map(int, raw_input().split())
    if n | m | a  == 0:
        break
    L = sorted([map(int, raw_input().split()) for _ in xrange(m)])
    A = range(n + 1)
    for h, p, q in L:
        A[p], A[q] = A[q], A[p]
    print A[a]

Submission status: Accepted

Solution code:
while 1:
	n,m,a = map(int,raw_input().split())
	if n == 0: break
	amida = [[] for i in range(n)]
	for i in range(m):
		h,p,q = map(int,raw_input().split())
		amida[p-1].append([h,q])
		amida[q-1].append([h,p])
	for i in range(n):
		amida[i] = sorted(amida[i],reverse=True)
	y = 1001
	while 1:
		for i in range(len(amida[a-1])):
			if amida[a-1][i][0] < y:
				y = amida[a-1][i][0]
				a = amida[a-1][i][1]
				break
		else:
			break
	print a

Submission status: Accepted

Solution code:
while True :
    n, m, a = map(int, input().split())
    if n == 0 and m == 0 and a == 0 :
        break
    
    org_num = []
    for i in range(n) :
        org_num.append(i+1)
        
    amida = []
    for i in range(m) :
        h, p, q = map(int, input().split())
        amida.append([h, p, q])
    amida.sort(reverse=True) # 横線の高い順にソート
    
    for i in range(m) :
        org_num[amida[i][1]-1], org_num[amida[i][2]-1] = org_num[amida[i][2]-1], org_num[amida[i][1]-1]
    
    print(org_num.index(a)+1)

Submission status: Accepted

Solution code:
horizontalLineList = []

while True:
    # 縦線の本数，横線の本数，調べる縦線の番号
    n, m, a = list(map(int, input().split()))

    if n == m == a == 0:
        break

    # 現在の縦線位置
    current = a

    horizontalLineList.clear()
    for _ in range(m):
        # hはその横線の高さ。
        # p, qはその横線につながっている2本の縦線の番号
        h, p, q = list(map(int, input().split()))

        horizontalLineList.append([h, p, q])

    # 横線の高さを昇順ソート
    horizontalLineList.sort(key=lambda x: x[0])

    targetHeight = 1000 + 1
    moved = False
    while horizontalLineList:
        h, p, q = horizontalLineList.pop()

        if (targetHeight == h) and moved:
            continue
        elif targetHeight != h:
            targetHeight = h
            moved = False
        
        if p == current:
            current = q
            moved = True
        elif q == current:
            current = p
            moved = True

    print(current)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    while 1:
        n,m,a=MI()
        if (n,m,a)==(0,0,0):break
        to={}
        max_h=0
        for _ in range(m):
            h,p,q=MI()
            max_h=max(max_h,h)
            to[(h,p)]=q
            to[(h,q)]=p
        i=max_h+1
        j=a
        while i>0:
            i-=1
            if (i,j) in to:j=to[(i,j)]
        print(j)

main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve(n,m,a):
    if m == 0:
        print(a)
        return
    l = LIR(m)
    l.sort(key = lambda x:-x[0])
    x = l[0][0]
    for h,p,q in l:
        if x < h:
            continue
        if p == a:
            x = h-1
            a = q
        elif q == a:
            x = h-1
            a = p
    print(a)
    return

#Solve
if __name__ == "__main__":
    while 1:
        n,m,a = LI()
        if n == m == a == 0:
            break
        solve(n,m,a)

Submission status: Accepted

Solution code:
while True:
    n, m, a = [int(i) for i in input().split()]
    
    if n == 0 and m == 0 and a == 0:
        break
    else:
        horizons = [[int(i) for i in input().split()] for j in range(m)]
        horizons.sort(reverse=True, key=lambda x: x[0])
        
        res = [int(i) for i in range(1, n+1)]
        
        for i in horizons:
            i[1] -= 1
            i[2] -= 1
            res[i[1]], res[i[2]] = res[i[2]], res[i[1]]
        
        print(res.index(a) + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
while True:
    n, m, a = map(int, input().split())
    if n == 0:
        exit()
    hpq = sorted(list(map(int, input().split())) for _ in range(m))[::-1]
    for h, p, q in hpq:
        if a == p:
            a = q
        elif a == q:
            a = p
    print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    while True:
        n,m,a = map(int,input().split())
        if not n and not m and not a:
            return
        hlines = [tuple(map(int,input().split())) for _ in range(m)]
        hlines = sorted(hlines, key=lambda x: x[0], reverse=True)

        for h in range(hlines[0][0], -1, -1):
            for hline in hlines:
                if hline[0] == h:
                    if hline[1] == a:
                        a = hline[2]
                    elif hline[2] == a:
                        a = hline[1]

        print(a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
while True:
    n, m, a = map(int, input().split())
    if n==0 and m==0 and a==0:
        break

    branch = [[0 for _ in range(1001)] for _ in range(n+1)]
    for i in range(m):
        h, p, q = map(int, input().split())
        branch[p][h] = q
        branch[q][h] = p

    cur = a
    for i in range(1000, 0, -1):
        if branch[cur][i]:
            cur = branch[cur][i]
    print(cur)

Submission status: Accepted

Solution code:
while True:
    n,m,a=map(int,input().split())
    if n==0:break
    l=[list(map(int,input().split())) for _ in range(m)]
    l.sort(reverse=True)
    for l2 in l:
        if l2[1]==a:
            a=l2[2]
            continue
        elif l2[2]==a:
            a=l2[1]
    print(a)

Submission status: Accepted

Solution code:
while True:
    n, m, a = list(map(int, input().split()))
    if n == 0:
        break
    hpq = []
    for i in range(m):
        h, p, q = list(map(int, input().split()))
        hpq.append([h, p, q])
    hpq = sorted(hpq, key=lambda x: x[0], reverse=True)
    for i in reversed(range(1, hpq[0][0] + 1)):
        for j in range(m):
            if hpq[j][0] > i:
                continue
            elif hpq[j][0] < i:
                break
            elif hpq[j][0] == i and hpq[j][1] != a and hpq[j][2] != a:
                continue
            elif hpq[j][0] == i and hpq[j][1] != a and hpq[j][2] == a:
                a = hpq[j][1]
                break
            elif hpq[j][0] == i and hpq[j][1] == a and hpq[j][2] != a:
                a = hpq[j][2]
                break
    print(a)

Submission status: Accepted

Solution code:
while 1:
    n, m, a = map(int, input().split())
    if n == 0:
        break

    row = []
    for _ in range(m):
        tmp = list(map(int, input().split()))
        row.append(tmp)

    row = sorted(row, key=lambda x: -x[0])
    for r in row:
        if r[1] == a:
            a = r[2]
        elif r[2] == a:
            a = r[1]

    print(a)

Submission status: Accepted

Solution code:
# coding: utf-8
while 1:
    n,m,a=map(int,input().split())
    if n==0:
        break
    dic={}
    for i in range(1,1001):
        dic[i]=[]
    for i in range(m):
        h,p,q=map(int,input().split())
        dic[h].append((p,q))
        dic[h].append((q,p))
    h=1000
    pos=a
    while h>0:
        for d in dic[h]:
            if d[0]==pos:
                pos=d[1]
                break
        h-=1
    print(pos)

Submission status: Runtime Error

Solution code:
# coding: utf-8

def main():
  while True:
    (n, m, a) = map(int, raw_input().split(' '))
    if (n, m, a) == (0, 0, 0): break

    bars = []
    for i in range(m):
      (h, p, q) = map(int, raw_input().split(' '))
      bars.append((h, p, q))

    x = a
    while True:
      # Down step by step, and above bars are removed in each step
      next_bar = max([b for b in bars if b[1] == x or b[2] == x])
      x = next_bar[2] if next_bar[1] == x else next_bar[1]
      y = next_bar[0]
      map(lambda b: bars.remove(b), [b for b in bars if b[0] >= y])
      if bars == []: break
    print x

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        while True:
            n, m, a = map(int, raw_input().split())
            if n == 0 and m == 0 and a == 0:
                break
            adj = [[] for i in range(m)]
            for i in range(m):
                h, p, q = map(int, raw_input().split())
                adj[h].append((p, q))

            for e in reversed(adj):
                for p, q in e:
                    if p == a:
                        a = q
                    elif q == a:
                        a = p
            print a
                    
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Runtime Error

Solution code:
while True:
    n, m, a = map(int, input().split())
    if n == 0: break
    ls = [[0 for i in range(n+1)] for i in range(m)]
    print(ls)
    for i in range(m):
        h, p, q = map(int, input().split())
        ls[h][p] = 1
    ls.reverse()
    print(ls)
    for t in ls:
        if t[a] == 1:
            a += 1
        elif t[a-1] == 1:
            a -= 1
    print(a)

Submission status: Runtime Error

Solution code:
if __name__ == "__main__":
    while True:
        n, m, a = map(int, raw_input().split())
        if n == 0 and m == 0 and a == 0:
            break

        now = a
        amida = [[] for i in range(1000)]

        for i in range(m):
            h, p, q = map(int, raw_input().split())
            amida[h].append((p, q))
        
        for height in range(1000 - 1, 0, -1):
            lines = amida[height]
            for l in lines:
                if l[0] == now:
                    now = l[1]
                elif l[1] == now:
                    now = l[0]

        print now

Submission status: Runtime Error

Solution code:
while True:
    n, m, a = map(int, input().split())

    if n + m + a == 0:
        break

    lines = list(reversed(sorted([tuple(map(int, input().split())) for _ in range(m)])))

    replace = list(range(1, n+1))

    for l in lines:
        h, p, q = l

        p -= 1
        q -= 1

        replace[p], replace[q] = replace[q], replace[p]

    a -= 1

    for _ in range(n):
        a = replace[a]

    print(a)

Submission status: Runtime Error

Solution code:
while True:
    [n,m,a]=input().split()
    if [n,m,a]==["0","0","0"]: break
    [n,m,a]=[int(n),int(m),int(a)]
    yokobo={}
    for k in range(m):
        [h,p,q]=input().sprit()
        yokobo[h,p]=[int(q)]
        yokobo[h,q]=[int(p)]
    move=1000
    while move>0:
        a=yokobo[move,a]
        move=move-1

Submission status: Runtime Error

Solution code:
while True:
  n,m,a = map(int, raw_input().split())
  if n==m==a==0: break
  lst = [0] * n
  for i in xrange(n):
    lst[i] = i
  ms = {}
  for _ in xrange(n):
    h,p,q = map(int, raw_input().split())
    if h not in ms:
      ms[h] = {}
    ms[h][p] = q
  for i,v in sorted(ms.items()):
    for k,l in v.items():
      tmp = lst[k-1]
      lst[k-1] = lst[l-1]
      lst[l-1] = tmp
  print lst[a-1]+1

Submission status: Runtime Error

Solution code:
while True:
	n, m, a = map(int, input().split())
	if (not (n or m or a)):
		break
	amida = [[] for i in range(n)]
	for i in range(n):
		h, p, q = map(int, input().split())
		amida[p-1].append((h, q-1))
		amida[q-1].append((h, p-1))
	for i in range(n):
		amida[i].sort()
	a -= 1
	h = 1000
	while amida[a]:
		h2, a2 = amida[a].pop()
		while h2 >= h and amida[a]:
			h2, a2 = amida[a].pop()
		if h2 < h:
			h, a = (h2, a2)
	print(a+1)

Submission status: Runtime Error

Solution code:
while True:
	n,m,a = map(int,input().split())
	if n == m == a == 0:
		break
	A = [[0]*1002 for i in range(n + 1)]
	for i in range(m + 1):
		h,p,q = map(int,input().split())
		A[p][1001 - h] = q
		A[q][1001 - h] = p
		
	for i in range(1001):
		if A[a][i] == 0:
			pass
		else:
			a = A[a][i]
	print(a)

Submission status: Runtime Error

Solution code:
N,M,A = map(int,input().split())
amd = [{} for i in range(1001)]
for i in range(M):
    h,p,q = map(int,input().split())
    amd[h][p] = q
    amd[h][q] = p
raw_input() #ignore

now = A
for d in reversed(amd):
    if now in d:
        now = d[now]
print(now)

Submission status: Runtime Error

Solution code:
N = 10**6

N1 = [i for i in range(N+40)]
N2 = [i for i in range(N+40)]

#N1[0] = 0
#N2[0] = 0

p = [n*(n+1)*(n+2)//6 for n in range(1,200) if n *(n+1)*(n+2)//6< N+1]
p2 = [n*(n+1)*(n+2)//6 for n in range(1,200) if n *(n+1)*(n+2)//6< N+1 and n *(n+1)*(n+2)//6 % 2 ==1 ]
#print(p2)
for p_ in p:
    if p_ > N +1:
        continue
    n = min(p_*5,10**6)
    for j in range(p_,n):
#        print(j)
        if N1[j] > N1[j-p_] +1:
            N1[j] = N1[j-p_]+1
for p_ in p2:
    if p_ > N +1 :
        continue
    for j in range(p_,N +1):
        if N2[j] > N2[j-p_]+1:
            N2[j] = N2[j -p_]+1
print('a')
while True:
    n = int(input())
    if n == 0:
        break
    print(N1[n],N2[n])

Submission status: Runtime Error

Solution code:
n, m, a = [int(x) for x in raw_input().strip().split()]

lines = []
while True:
  h, p, q = [int(x) for x in raw_input().strip().split()]
  if h == p == q == 0:
    break
  else:
    lines.append([h, p, q])

verticals = [[] for i in xrange(n)]
for i in xrange(n):
  for l in lines:
    if l[1] == i + 1 or l[2] == i + 1:
      verticals[i].append(l)
  t = sorted(verticals[i], reverse = True)
  verticals[i] = t

def solve(height, pos):
  for line in verticals[pos - 1]:
    if line[0] < height:
      height = line[0]
      if line[1] == pos:
        pos = line[2]
      else:
        pos = line[1]
      return solve(height, pos)
  print pos
  return

solve(10000, a)

Submission status: Runtime Error

Solution code:
while 1:
        num=map(int,raw_input().split())
        if num==[0,0,0] : break
        hrz=[0 for i in range(num[1])]
        for i in range(num[1]):
                hrz[i]=map(int,raw_input().split())
        lct=[1001,num[2]]
        while lct[0]!=1:
                pps=[0,0]
                for i in range(num[1]):
                        if pps[0]<hrz[i][0]<lct[0]:
                                if hrz[i][1]==lct[1]:
                                        pps=[hrz[i][0],hrz[i][2]]
                                elif hrz[i][2]==lct[1]:
                                        pps=[hrz[i][0],hrz[i][1]]
                lct=pps
        print lct[1]