Problem Statement

You are given N strings S_1,S_2,\ldots,S_N in this order.

Print S_N,S_{N-1},\ldots,S_1 in this order.

Constraints

• 1\leq N \leq 10
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters, uppercase English letters, and digits.

Sample Input 1

3
Takahashi
Aoki
Snuke

Sample Output 1

Snuke
Aoki
Takahashi

We have N=3, S_1= Takahashi, S_2= Aoki, and S_3= Snuke.

Thus, you should print Snuke, Aoki, and Takahashi in this order.

Sample Input 2

4
2023
Year
New
Happy

Sample Output 2

Happy
New
Year
2023

The given strings may contain digits.

Problem Statement

In this problem, an input file contains multiple test cases.
You are first given an integer T. Solve the following problem for T test cases.

• We have N positive integers A_1, A_2, ..., A_N. How many of them are odd?

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

Sample Output 1

2
1
5
0

This input contains four test cases.

The second and third lines correspond to the first test case, where N = 3, A_1 = 1, A_2 = 2, A_3 = 3.
We have two odd numbers in A_1, A_2, and A_3, so the first line should contain 2.

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

• 1 \leq N \leq 100
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq u_i, v_i \leq N
• The given graph is simple.
• All values in the input are integers.

Sample Input 1

5 3
1 2
1 3
4 5

Sample Output 1

2

The given graph contains the following two connected components:

• a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
• a subgraph formed from vertices 4, 5, and edge 3.

Sample Input 2

5 0

Sample Output 2

5

Sample Input 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 3

1

Problem Statement

You are given a positive integer N. It is known that N can be represented as N=p^2q using two different prime numbers p and q.

Find p and q.

You have T test cases to solve.

Constraints

• All values in the input are integers.
• 1\leq T\leq 10
• 1\leq N \leq 9\times 10^{18}
• N can be represented as N=p^2q using two different prime numbers p and q.

Sample Input 1

3
2023
63
1059872604593911

Sample Output 1

17 7
3 7
104149 97711

For the first test case, we have N=2023=17^2\times 7. Thus, p=17 and q=7.

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i. The degree of each vertex is at most 10.
Let K be the number of simple paths (paths without repeated vertices) starting from vertex 1. Print \min(K, 10^6).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2}\right)
• 1 \leq u_i, v_i \leq N
• The given graph is simple.
• The degree of each vertex in the given graph is at most 10.
• All values in the input are integers.

Sample Input 1

4 2
1 2
2 3

Sample Output 1

3

We have the following three paths that count. (Note that a path of length 0 also counts.)

• Vertex 1;
• vertex 1, vertex 2;
• vertex 1, vertex 2, vertex 3.

Sample Input 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

16

Sample Input 3

8 21
2 6
1 3
5 6
3 8
3 6
4 7
4 6
3 4
1 5
2 4
1 2
2 7
1 4
3 5
2 5
2 3
4 5
3 7
6 7
5 7
2 8

Sample Output 3

2023

Problem Statement

For a string S of length N and an integer i\ (0\leq i\leq N), let us define the string f_i(S) as the concatenation of:

• the first i characters of S,
• the reversal of S, and
• the last (N-i) characters of S,

in this order. For instance, if S= abc and i=2, we have f_i(S)= abcbac.

You are given a string T of length 2N. Find a pair of a string S of length N and an integer i\ (0\leq i\leq N) such that f_i(S)=T. If no such pair of S and i exists, report that fact.

Constraints

• 1\leq N \leq 10^6
• N is an integer.
• T is a string of length 2N consisting of lowercase English letters.

Sample Input 1

3
abcbac

Sample Output 1

abc
2

As mentioned in the problem statement, if S= abc and i=2, we have f_i(S)= abcbac, which equals T, so you should print abc and 2.

Sample Input 2

4
abababab

Sample Output 2

abab
1

S= abab and i=3 also satisfy the condition.

Sample Input 3

3
agccga

Sample Output 3

cga
0

S= agc and i=3 also satisfy the condition.

Sample Input 4

4
atcodeer

Sample Output 4

-1

If no pair of S and i satisfies the condition, print -1.

Problem Statement

For a sequence of length N, A = (A_1,A_2,\dots,A_N), consisting of integers between 1 and N, inclusive, and an integer i\ (1\leq i \leq N), let us define a sequence of length 10^{100}, B_i=(B_{i,1},B_{i,2},\dots,B_{i,10^{100}}), as follows.

• B_{i,1}=i.
• B_{i,j+1}=A_{B_{i,j}}\ (1\leq j<10^{100}).

Additionally, let us define S_i as the number of distinct integers that occur exactly once in the sequence B_i. More formally, S_i is the number of values k such that exactly one index j\ (1\leq j\leq 10^{100}) satisfies B_{i,j}=k.

You are given an integer N. There are N^N sequences that can be A. Find the sum of \displaystyle \sum_{i=1}^{N} S_i over all of them, modulo M.

Constraints

• 1\leq N \leq 2\times 10^5
• 10^8\leq M \leq 10^9
• N and M are integers.

Sample Input 1

4 100000000

Sample Output 1

624

As an example, let us consider the case A=(2,3,3,4).

• For i=1: we have B_1=(1,2,3,3,3,\dots), where two integers, 1 and 2, occur exactly once, so S_1=2.
• For i=2: we have B_2=(2,3,3,3,\dots), where one integer, 2, occurs exactly once, so S_2=1.
• For i=3: we have B_3=(3,3,3,\dots), where no integers occur exactly once, so S_3=0.
• For i=4: we have B_4=(4,4,4,\dots), where no integers occur exactly once, so S_4=0.

Thus, we have \displaystyle \sum_{i=1}^{N} S_i=2+1+0+0=3.

If we similarly compute \displaystyle \sum_{i=1}^{N} S_i for the other 255 sequences, the sum of this value over all 256 sequences is 624.

Sample Input 2

7 1000000000

Sample Output 2

5817084

Sample Input 3

2023 998244353

Sample Output 3

737481389

Print the sum modulo M.

Sample Input 4

100000 353442899

Sample Output 4

271798911

Problem Statement

You are to generate a graph by the following procedure.

• Choose a simple undirected graph with N unlabeled vertices.
• Write a positive integer at most K in each vertex in the graph. Here, there must not be a positive integer at most K that is not written in any vertex.

Find the number of possible graphs that can be obtained, modulo P. (P is a prime.)

Two graphs are considered the same if and only if one can label the vertices in each graph as v_1, v_2, \dots, v_N to satisfy the following conditions.

• For every i such that 1 \leq i \leq N, the numbers written in vertex v_i in the two graphs are the same.
• For every i and j such that 1 \leq i \lt j \leq N, there is an edge between v_i and v_j in one of the graphs if and only if there is an edge between v_i and v_j in the other graph.

Constraints

• 1 \leq K \leq N \leq 30
• 10^8 \leq P \leq 10^9
• P is a prime.
• All values in the input are integers.

Sample Input 1

3 1 998244353

Sample Output 1

4

The following four graphs satisfy the condition.

Sample Input 2

3 2 998244353

Sample Output 2

12

The following 12 graphs satisfy the condition.

Sample Input 3

5 5 998244353

Sample Output 3

1024

Sample Input 4

30 15 202300013

Sample Output 4

62712469