Problem Statement

You are given a simple undirected graph G with N vertices numbered 1 to N. G has M edges and the i-th edge connects vertices A_i and B_i.

Check if G satisfies the following condition:

• For every subset X of the vertex set \{1,2,\cdots,N\}, there exists a subset Y of X such that |Y|\ge \frac{|X|}{2} and Y forms a clique.

You have T testcases to solve.

Constraints

• 1\le T \le 10^3
• 1\le N \le 10^5
• 0 \le M \le 10^6
• 1 \le A_i,B_i \le N
• The given graph doesn't contain self-loops or multiple edges.
• The sum of N across the test cases in a single input is at most 10^5.
• The sum of M across the test cases in a single input is at most 10^6.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
Yes
Yes
No

For the 1-st test case, G satisfies the condition. In this case, every subset X is a clique, so we can just let Y=X.

For the 2-nd test case, G satisfies the condition. For example, for X=\{2,3\}, we can let Y=\{2\}.

For the 4-th test case, G doesn't satisfy the condition. If we let X=\{1,2,3\}, no subset Y of X satisfies the condition.

Problem Statement

You have an integer sequence a=(a_1,a_2,\cdots,a_N) of length N. All elements are initially 0.

You are given an integer C and M intervals ([L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M]).

You will choose a permutation p of (1,2,\cdots,M) and an integer sequence w=(w_1,w_2,\cdots,w_M) of length M. Here, 1\le w_i\le C must hold.

Then, you will do M modifications. The i-th modification is the following:

• Change a_{L_{p_i}}, \cdots, a_{R_{p_i}} to w_i.

It is guaranteed that every position in a is covered by at least one interval.

Find the number of achievable a after all modifications. Print the answer modulo 998244353.

Constraints

• 1\le N\le 100
• 1\le M\le\dfrac{N(N+1)}{2}
• 1\le C<998244353
• 1 \le L_i \le R_i \le N
• (L_i,R_i) \neq (L_j,R_j) (i \neq j)
• Every position in a is covered by at least one interval.
• All input values are integers.

Sample Input 1

5 5 2
1 3
2 2
3 3
1 5
3 5

Sample Output 1

16

There are 16 sequences that can be achieved. For example, you can achieve a=(2,1,1,1,1) in the following manner:

• Choose p=(4,1,2,3,5) and w=(1,2,1,2,1)
• The 1-st operation changes a into (1,1,1,1,1)
• The 2-nd operation changes a into (2,2,2,1,1)
• The 3-rd operation changes a into (2,1,2,1,1)
• The 4-th operation changes a into (2,1,2,1,1)
• The 5-th operation changes a into (2,1,1,1,1)

Sample Input 2

20 30 20
1 14
1 7
1 16
3 13
1 17
4 8
2 11
4 12
9 14
3 15
11 19
1 13
4 15
8 19
3 17
15 18
10 18
1 18
17 19
16 20
1 8
8 15
13 17
1 19
13 19
1 20
6 13
10 12
11 20
17 18

Sample Output 2

258066445

Problem Statement

We call an infinite sequence of positive integers (a_1,a_2,\cdots) good if and only if it satisfies both of the following conditions:

• There exists a finite constant C such that a_n \le C \cdot n for all 1 \le n;

• For all pairs of positive integers (n,m), a_n \mid a_m if and only if n\mid m. Here, x \mid y means x divides y.

You are given a positive integer sequence A=(A_1,A_2,\cdots,A_N) of length N. Check if there exists a good infinite sequence starting with (A_1,A_2,\cdots,A_N).

You have T testcases to solve.

Constraints

• 1\le T \le 5000
• 1 \leq N \leq 5000
• 1 \leq A_i \leq 10^{18}
• The sum of N across the test cases in a single input is at most 5000.
• All input values are integers.

Sample Input 1

5
5
1 2 3 4 5
5
1 4 9 16 25
5
1 4 6 8 10
5
1 2 4 4 5
5
1 2 3 5 4

Sample Output 1

Yes
Yes
Yes
No
No

For the 1-st test case, we can let a_n=n and that satisfies the condition.

Problem Statement

You are given an integer N and prime P.

We call a sequence of N intervals ([L_1,R_1] ,[L_2,R_2], \cdots, [L_N,R_N]) good if and only if both of the followings are satisfied:

• 1\le L_i\le R_i\le N holds for all 1\le i\le N.
• There exists a unique permutation x=(x_1,x_2,\cdots,x_N) of (1,2,\cdots,N) such that L_i\le x_i\le R_i holds for all 1\le i\le N.

Count the number, modulo P, of good sequences of intervals.

Constraints

• 2 \leq N \leq 5000
• 10^9<P<1.01\times 10^9
• P is prime.
• All input values are integers.

Sample Input 1

2 1005488041

Sample Output 1

6

The following 6 sequences are good:

• ([1,1],[2,2])
• ([1,2],[2,2])
• ([1,1],[1,2])
• ([2,2],[1,1])
• ([2,2],[1,2])
• ([1,2],[1,1])

Sample Input 2

5 1005488041

Sample Output 2

102960

Sample Input 3

100 1005488041

Sample Output 3

47599495

Sample Input 4

1000 1005488041

Sample Output 4

632708165

Problem Statement

You are given an integer N and a prime P.

Count the number, modulo P, of undirected connected graphs G of N vertices numbered 1 to N that satisfy the following condition:

• There are no self-loops in G. Note that multiple edges are allowed.
• For all edges (u,v) in G, if we delete (u,v) from G, G remains connected. In other words, G is edge-biconnected.
• For all edges (u,v) in G, if we delete (u,v) from G, G is no longer edge-biconnected.

Two graphs are considered different if and only if there exists a pair of distinct vertices (u,v) such that the numbers of edges connecting u and v in the two graphs are different.

Constraints

• 2 \le N \le 50
• 10^9<P<1.01\times 10^9
• P is prime.
• All input values are integers.

Sample Input 1

2 1005976817

Sample Output 1

1

Sample Input 2

5 1000837403

Sample Output 2

372

Sample Input 3

10 1001160547

Sample Output 3

789846604

Sample Input 4

20 1006779551

Sample Output 4

888612770