Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
• All values in the input are integers.
• The graph given in the input is simple.

Sample Input 1

4 3
1 3
4 2
3 2

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

Sample Input 3

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

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

Problem Statement

You are given N strings S_1,\ldots,S_N.

For a sequence (A_1,\ldots,A_K) of length K where all elements are between 1 and N, inclusive, define the string f(A_1,\ldots,A_K) as S_{A_1}+S_{A_2}+\dots+S_{A_K}. Here, + represents string concatenation.

When all f(A_1,\dots,A_K) for the N^K sequences are sorted in lexicographical order, find the X-th smallest string.

Constraints

• 1\leq N \leq 10
• 1\leq K \leq 5
• 1\leq X \leq N^K
• S_i is a string consisting of lowercase English letters with length at most 10.
• N, K, and X are all integers.

Sample Input 1

3 2 6
abc
xxx
abc

Sample Output 1

abcxxx

• f(1,1)= abcabc
• f(1,2)= abcxxx
• f(1,3)= abcabc
• f(2,1)= xxxabc
• f(2,2)= xxxxxx
• f(2,3)= xxxabc
• f(3,1)= abcabc
• f(3,2)= abcxxx
• f(3,3)= abcabc

When these are sorted in lexicographical order: abcabc, abcabc, abcabc, abcabc, abcxxx, abcxxx, xxxabc, xxxabc, xxxxxx, the 6-th is abcxxx.

Sample Input 2

5 5 416
a
aa
aaa
aa
a

Sample Output 2

aaaaaaa

Problem Statement

There is a grid of H rows and W columns, each cell having a side length of 1, and we have N tiles.
The i-th tile (1\leq i\leq N) is a rectangle of size A_i\times B_i.
Determine whether it is possible to place the tiles on the grid so that all of the following conditions are satisfied:

• Every cell is covered by exactly one tile.
• It is fine to have unused tiles.
• The tiles may be rotated or flipped when placed. However, each tile must be aligned with the edges of the cells without extending outside the grid.

Constraints

• 1\leq N\leq 7
• 1 \leq H,W \leq 10
• 1\leq A_i,B_i\leq 10
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

Placing the 2-nd, 4-th, and 5-th tiles as shown below covers every cell of the grid by exactly one tile.

Hence, print Yes.

Sample Input 2

1 1 2
2 3

Sample Output 2

No

It is impossible to place the tile without letting it extend outside the grid.
Hence, print No.

Sample Input 3

1 2 2
1 1

Sample Output 3

No

It is impossible to cover all cells with the tile.
Hence, print No.

Sample Input 4

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

Sample Output 4

No

Note that each cell must be covered by exactly one tile.

Problem Statement

Consider the following procedure of, given a string X consisting of lowercase English alphabets, obtaining a new string:

• Split the string X off at the positions where two different characters are adjacent to each other.
• For each string Y that has been split off, replace Y with a string consisting of the character which Y consists of, followed by the length of Y.
• Concatenate the replaced strings without changing the order.

For example, aaabbcccc is divided into aaa,bb,cccc, which are replaced by a3,b2,c4, respectively, which in turn are concatenated without changing the order, resulting in a3b2c4.If the given string is aaaaaaaaaa , the new string is a10 .

Find the number, modulo P, of strings S of lengths N consisting of lowercase English alphabets, such that the length of T is smaller than that of S, where T is the string obtained by the procedure above against the string S.

Constraints

• 1 \le N \le 3000
• 10^8 \le P \le 10^9
• N and P are integers.
• P is a prime.

Sample Input 1

3 998244353

Sample Output 1

26

Those strings of which the 1-st, 2-nd, and 3-rd characters are all the same satisfy the condition.

For example, aaa becomes a3, which satisfies the condition, while abc becomes a1b1c1, which does not.

Sample Input 2

2 998244353

Sample Output 2

0

Note that if a string is transformed into another string of the same length, such as aa that becomes a2, it does not satisfy the condition.

Sample Input 3

5 998244353

Sample Output 3

2626

Strings like aaabb and aaaaa satisfy the condition.

Sample Input 4

3000 924844033

Sample Output 4

607425699

Find the number of strings satisfying the condition modulo P.

Problem Statement

For a sequence X=(X_1,X_2\ldots,X_N) of length N consisting of positive integers, we define f(X) as follows:

• A tree with N vertices is said to be good if and only if the degree of the i-th (1 \leq i \leq N) vertex is X_i. If a good tree exists, f(X) is the maximum diameter of a good tree; if it doesn't, f(X)=0.

Here, the distance between two vertices is the minimum number of edges that must be traversed to travel from one vertex to the other, and the diameter of a tree is the maximum distance between two vertices.

Find the sum, modulo 998244353, of f(X) over all possible sequences X of length N consisting of positive integers. We can prove that the sum of f(X) is a finite value.

Given T test cases, find the answer for each of them.

Constraints

• 1\leq T \leq 2\times 10^5
• 2 \leq N \leq 10^6
• All values in the input are integers.

Sample Input 1

10
2
3
5
8
13
21
34
55
89
144

Sample Output 1

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

If N=3,

for example,

• when X=(1,1,1), there is no tree with three vertices whose degrees are 1,1, and 1, so f(X)=0.
• When X=(2,1,1), the only possible tree is illustrated below. The diameter of this tree is 2, so f(X)=2.

For X=(2,1,1),(1,2,1),(1,1,2), we have f(X)=2; for other X, we have f(X)=0. Thus, the answer is 6.