问题1210--Mouse and Parenthesis

1210: Mouse and Parenthesis

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

提交

题目描述

Tom has m same balanced parenthesis sequence P=p1 p2…pn of length n.

This day Jerry comes into Tom's room and swaps one pair of parenthesis in every sequence.

Tom and Jerry both like balanced parenthesis sequence, so Jerry wants to know whether each P remains balanced after pai and pbi  swapped. 


Parenthesis sequence S is balanced if and only if:
1. S is empty;
2. or there exists balanced parenthesis sequence A,B such that S=AB;
3. or there exists balanced parenthesis sequence S' such that S=(S').

输入

The first line contains an integers T (T≤20), which indicates the number of test cases

For each case:

The first line contains two integers n,m.
The second line contains n characters p1 p2…pn.

The i-th of the last m lines contains 2 integers ai,bi (1≤ai,bi≤n,ai≠bi).


⋅ for 50% data, 1≤n≤50,1≤q≤1000.

⋅ for 100% data, 1≤n≤100000,1≤q≤100000.

输出

For every test case, you should output "Case #x:", where x indicates the case number and counts from 1. Then in ith line output 'Yes' if ith parenthesis sequence is balanced, otherwise 'No'. 

样例输入 Copy

2
4 2
(())
1 3
2 3
2 1
()
1 2

样例输出 Copy

Case #1:
No
Yes
Case #2:
No

来源/分类