F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

color

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 169    Accepted Submission(s): 21

Problem Description
You are given a directed graph, which is constructed as follows:
+ Pick an connected undirected graph with exactly n vertices and n edges. The vertices are numbered 1 through n.
+ Convert each undirected edge into a directed edge, satisfying each vertice's outdegree equals 1.

Also you're given m different colors to color the vertices. Your task is to calculate the number of different colored graphs that can be made.

Two colored graphs A and B are considered the same if and only if there exists a mapping P satisfying the following constraints:

+ Vertice u in graph A has the same color as vertice P(u) in graph B.
+ For any two different vertices u and v in graph A, P(u) and P(v) are different vertices in graph B.
+ For any directed edge u -> v in graph A, there exists a corresponding directed edge P(u) -> P(v) in graph B.

Print the answer module 10^9 + 7.

Input
The first line contains a number T(1 <= T <= 10), denoting the number of testcases.

For each testcase, the first line contains two space-seperated integers n and m(3 <= n <= 10^5, 1 <= m <= 10^9), representing the number of vertices in the graph and the number of colors you have.

Then, n lines follow. The i-th of them contains an integer f_i, denoting a directed edge from vertice i to vertice f_i in the given graph.(1 <= f_i <= n, f_i != i)

Output
For each testcase, print a line containing the answer.

Sample Input
1
6 3
2
3
4
1
1
3

Sample Output
378

Author

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-07-14 09:06:40, Gzip enabled Administration