1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def main():
    n, m, s = map(int, input().split())

    right = []
    left = []

    for _ in range(m):
        a, b = map(int, input().split())
        if a == b == s:
            continue
        if a == s:
            a = s+1
        if b == s:
            b = s-1
        if a < s < b:
            right.append((s+1, b))
            left.append((a, s-1))
        elif a > s:
            right.append((a, b))
        else:
            left.append((a, b))

    right.sort(key=lambda pair_: pair_[0])
    left.sort(key=lambda pair_: pair_[0], reverse=True)

    min_ = 1e13
    dom = 0

    last = s

    for pair in left:
        if pair[1] != last - 1:
            break

        last = pair[0]

    if last != 1:
        min_ = s - (last - 1)
        dom = last - 1

    last = s

    for pair in right:
        if pair[0] != last + 1:
            break

        last = pair[1]

    if last != n and min_ > last + 1 - s:
        dom = last + 1

    print(dom)

if __name__ == "__main__":
    main()