Problem:


Score : 100 points

Problem Statement

You have N cups and 1 ball.

The cups are arranged in a row, from left to right.

You turned down all the cups, then inserted the ball into the leftmost cup.

Then, you will perform the following Q operations:

The i-th operation: swap the positions of the A_i-th and B_i-th cups from the left. If one of these cups contains the ball, the ball will also move.

Since you are a magician, you can cast a magic described below:

Magic: When the ball is contained in the i-th cup from the left, teleport the ball into the adjacent cup (that is, the (i-1)-th or (i+1)-th cup, if they exist).

The magic can be cast before the first operation, between two operations, or after the last operation, but you are allowed to cast it at most once during the whole process.

Find the number of cups with a possibility of containing the ball after all the operations and possibly casting the magic.

Constraints

2 \leq N \leq 10^5

1 \leq Q \leq 10^5

1 \leq A_i < B_i \leq N

Input

The input is given from Standard Input in the following format:

N Q
A_1 B_1
A_2 B_2
:          
A_Q B_Q

Output

Print the number of cups with a possibility of eventually containing the ball.

Sample Input 1

10 3
1 3
2 4
4 5

Sample Output 1

4

Sample Input 2

20 3
1 7
8 20
1 19

Sample Output 2

5



Sample input:
10 3
1 3
2 4
4 5


Sample output:
4

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
p=[i for i in range(n)]
v=[0]*n
v[1],v[0]=1,1
t=0
for i in range(q):
    a,b=map(lambda x:int(x)-1,input().split())
    if t==b:t=a
    if t==a:t=b
    p[a],p[b]=p[b],p[a]
    if 0<=t+1<n:v[p[t+1]]=1
    if 0<=t-1<n:v[p[t-1]]=1
print(sum(v))

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
p=[i for i in range(n)]
v=[0]*n
v[1]=1
t=0
for i in range(q):
    a,b=map(lambda x:int(x)-1,input().split())
    if p[b]==t:t=p[a]
    if p[a]==t:t=p[b]
    p[a],p[b]=p[b],p[a]
    if 0<=t+1<n:v[p[t+1]]=1
    if 0<=t-1<n:v[p[t-1]]=1
print(sum(v))

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
p=[i for i in range(n)]
v=[1,1]+[0]*(n-2)
t=0
for i in range(q):
    a,b=map(lambda x:int(x)-1,input().split())
    if p[b]==t:t=p[a]
    if p[a]==t:t=p[b]
    p[a],p[b]=p[b],p[a]
    if 0<=t+1<n:v[p[t+1]]=1
    if 0<=t-1<n:v[p[t-1]]=1
print(sum(v))

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
p=[i for i in range(n)]
v=[1,1]+[0]*(n-2)
t=0
for i in range(q):
    a,b=map(lambda x:int(x)-1,input().split())
    if p[b]==t:t=p[a]
    if p[a]==t:t=p[b]
    p[a],p[b]=p[b],p[a]
    if 0<=t+1<n:v[p[t+1]]=1
    if 0<=t-1<n:v[p[t-1]]=1
print(sum(v))

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
AB=[list(map(int,input().split()))for _ in range(Q)]

ans=1
anls=set([1])
ansidx=0
ray=[e for  e  in range(0,N)]
anls.add(ray[1])

for e,(a,b) in enumerate(AB ):
  a,b=a-1,b-1
  ray[a],ray[b]=ray[b],ray[a]
  if ansidx!=0:
    anls.add(ray[ansidx-1])
  if ansidx  !=N-1:
    anls.add(ray[ansidx+1])
print(len(anls))

Submission status: Wrong Answer

Solution code:
n,q=map(int,raw_input().split())
exist=[1,2]
cup=range(n+2)
now=1
for i in xrange(q):
    a,b=map(int,raw_input().split())
    if now==a:
        exist.append(cup[a-1])
        exist.append(cup[a+1])
        now=b
    elif now==b:
        exist.append(cup[b-1])
        exist.append(cup[b+1])
        now=a
    tmp=cup[a]
    cup[a]=cup[b]
    cup[b]=tmp
exist.append(now-1)
exist.append(now+1)
exist=list(set(exist))
ans=0
for i in xrange(len(exist)):
    if exist[i]!=0 or exist[i]!=n+1 :ans+=1
print ans

Submission status: Time Limit Exceeded

Solution code:
j=lambda:map(int,raw_input().split())
n,q=j()
u=1
c=[1]*3+[0]*(n-2)+[1]
exec("a,b=d=j();u+=u in d and a+b-2*u;c[a],c[b]=c[b],c[a];c[u-1]=c[u+1]=1;"*q)
print sum(c)-2

Submission status: Time Limit Exceeded

Solution code:
j=lambda:map(int,raw_input().split())
n,q=j()
c=[1,-1,1]+[0]*(n-2)+[1]
for p in[-1]*q:a,b=j();c[a],c[b]=c[b],c[a];i=c.index(p);c[i-1]=c[i+1]=1
print sum(c)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
L=[i for i in range(N+2)]
P=1
C=[0 for i in range(N+2)]
C[P-1]=1
C[P+1]=1
C[P]=1
for i in range(Q):
    A,B=map(int,input().split())
    if A==P:
        P=B
    elif B==P:
        P=A
    L[A],L[B]=L[B],L[A]
    C[L[P-1]]=1
    C[L[P+1]]=1
ans=0
for i in range(1,N+1):
    if C[i]==1:
        ans+=1
print(ans)
#print(L)
#print(C)

Submission status: Accepted

Solution code:
n, q = [ int(v) for v in input().split() ]
num = [ 0 for i in range(n) ]
num[0] = 1
num[1] = 2
p = 0
for i in range(q):
    a, b = [ int(v)-1 for v in input().split() ]
    num[a], num[b] = num[b], num[a]
    if num[a] == 1:
        p = a
    elif num[b] == 1:
        p = b
    if p > 0:
        num[p-1] = 2
    if p < n-1:
        num[p+1] = 2
print(n - num.count(0))

Submission status: Accepted

Solution code:
n, q = [int(item) for item in input().split()]
ball = [0] * n
ball[0] = 1
ball[1] = 1
place = 0
for i in range(q):
    a, b = [int(item) - 1 for item in input().split()]
    if a == place:
        place = b
    elif b == place:
        place = a
    ball[a], ball[b] = ball[b], ball[a]
    if place - 1 >= 0:
        ball[place - 1] = 1
    if place + 1 < n:
        ball[place + 1] = 1
print(sum(ball))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(Q)]

cup = list(range(N+1)) + [0]
se = set([0,1,2])
ball = 1
for a,b in AB:
    cup[a],cup[b] = cup[b],cup[a]
    for x in [a,b]:
        if cup[x] == 1:
            ball = x
    se.add(cup[ball-1])
    se.add(cup[ball+1])

se.remove(0)
answer = len(se)
print(answer)

Submission status: Accepted

Solution code:
n,q = (int(i) for i in input().split())
now,x = 1,[0 for i in range(n+2)]
x[2] = 1
for i in range(q):
	a,b = (int(j) for j in input().split())
	if a==now or b==now: now=(a+b)-now
	if x[a]==1 and x[b]==1: pass
	elif x[a]==1: x[a],x[b] = 0,1
	elif x[b]==1: x[a],x[b] = 1,0
	x[now+1],x[now-1] = 1,1
x[now] = 1
print(sum(x[1:n+1]))

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
dp = [0] * (N+2)
dp[2] = 1
ball = 1
for i in range(Q):
    a,b = map(int,input().split())
    dp[a],dp[b] = dp[b],dp[a]
    if ball == a:
        ball = b
    elif ball == b:
        ball = a
    dp[ball-1] |= 1
    dp[ball+1] |= 1
dp[ball] |= 1
print(sum(dp[1:-1]))

Submission status: Accepted

Solution code:
n,q=map(int,raw_input().split())
exist=[False]*(n+2)
exist[1]=True
cup=range(n+2)
now=1
exist[cup[now-1]]=True
exist[cup[now+1]]=True
for i in xrange(q):
    a,b=map(int,raw_input().split())
    if now==a:now=b
    elif now==b:now=a
    tmp=cup[a]
    cup[a]=cup[b]
    cup[b]=tmp
    exist[cup[now-1]]=True
    exist[cup[now+1]]=True
ans=0
for i in xrange(1,n+1):
    if exist[i]:ans+=1
print ans

Submission status: Accepted

Solution code:
n,q=map(int,raw_input().split())
exist=set([1])
cup=range(n+2)
now=1
exist.add(cup[now-1])
exist.add(cup[now+1])
for i in xrange(q):
    a,b=map(int,raw_input().split())
    if now==a:now=b
    elif now==b:now=a
    tmp=cup[a]
    cup[a]=cup[b]
    cup[b]=tmp
    exist.add(cup[now-1])
    exist.add(cup[now+1])
exist=list(exist)
ans=0
for i in xrange(len(exist)):
    if exist[i]!=0 and exist[i]!=n+1:ans+=1
print ans

Submission status: Accepted

Solution code:
j=lambda:map(int,raw_input().split())
n,q=j()
u=1
c=[1]*3+[0]*(n-2)+[1]
for p in[-1]*q:a,b=d=j();u+=u in d and a+b-2*u;c[a],c[b]=c[b],c[a];c[u-1]=c[u+1]=1
print sum(c)-2

Submission status: Accepted

Solution code:
N, Q = map(int, raw_input().split())
possible = [False for _ in xrange(N)]
possible[0] = True
possible[1] = True
A = 0

for q in xrange(Q):
    a, b = map(lambda x:int(x)-1, raw_input().split())
    if a == A:
        A = b
    elif b == A:
        A = a
    possible[a], possible[b] = possible[b], possible[a]
    possible[max(0, A-1)] = True
    possible[min(N-1, A+1)] = True

print sum(possible)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(Q)]

cup = list(range(N+1)) + [0]
se = set([0,1,2])
for a,b in AB:
    cup[a],cup[b] = cup[b],cup[a]
    for x in [a,b]:
        if cup[x] == 1:
            ball = x
    se.add(cup[ball-1])
    se.add(cup[ball+1])

se.remove(0)
answer = len(se)
print(answer)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(Q)]

cup = list(range(N+1)) + [0]
se = set()
se.add(1)
se.add(2)
for a,b in AB:
    cup[a],cup[b] = cup[b],cup[a]
    for x in [a,b]:
        if cup[x] == 1:
            ball = x
    se.add(cup[ball-1])
    se.add(cup[ball+1])

se.discard(0)
answer = len(se)
print(answer)

Submission status: Runtime Error

Solution code:
 n,q=map(int,raw_input().split())
exist=set([1])
cup=range(n+2)
now=1
exist.add(cup[now-1])
exist.add(cup[now+1])
for i in xrange(q):
    a,b=map(int,raw_input().split())
    if now==a:now=b
    elif now==b:now=a
    tmp=cup[a]
    cup[a]=cup[b]
    cup[b]=tmp
    exist.add(cup[now-1])
    exist.add(cup[now+1])
exist.add(now-1)
exist.add(now+1)
exist=list(exist)
ans=0
for i in xrange(len(exist)):
    if exist[i]!=0 and exist[i]!=n+1:ans+=1
print ans

Submission status: Runtime Error

Solution code:
j=lambda:map(int,raw_input().split())
n,q=j()
u=1
c=[1]*3+[0]*(n-2)+[1]
exec("a,b=d=j();u+=u in d and a+b-2*u;c[a],c[b]=c[b],c[a];c[u-1]=c[u+1]=1"*q)
print sum(c)-2