F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4423. -- [AMPPZ2013]Bytehattan

4423: [AMPPZ2013]Bytehattan

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 778  Solved: 461
[Submit][Status][Discuss]

Description

比特哈顿镇有n*n个格点,形成了一个网格图。一开始整张图是完整的。
有k次操作,每次会删掉图中的一条边(u,v),你需要回答在删除这条边之后u和v是否仍然连通。

Input

第一行包含两个正整数n,k(2<=n<=1500,1<=k<=2n(n-1)),表示网格图的大小以及操作的个数。
接下来k行,每行包含两条信息,每条信息包含两个正整数a,b(1<=a,b<=n)以及一个字符c(c=N或者E)。
如果c=N,表示删除(a,b)到(a,b+1)这条边;如果c=E,表示删除(a,b)到(a+1,b)这条边。
数据进行了加密,对于每个操作,如果上一个询问回答为TAK或者这是第一个操作,那么只考虑第一条信息,否则只考虑第二条信息。
数据保证每条边最多被删除一次。

Output

输出k行,对于每个询问,如果仍然连通,输出TAK,否则输出NIE。

Sample Input

3 4
2 1 E 1 2 N
2 1 N 1 1 N
3 1 N 2 1 N
2 2 N 1 1 N

Sample Output

TAK
TAK
NIE
NIE

HINT

Source

鸣谢Claris提供试题

[Submit][Status][Discuss]

HOME Back