Universal Cup Judging System

Universal Cup

時間限制: 3 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Se te dan $m$ órdenes de búsqueda en profundidad (DFS) de un árbol con raíz desconocido.

Consideramos árboles con raíz con $n$ vértices etiquetados del $1$ al $n$, donde el vértice $1$ es la raíz. El árbol es no dirigido y conexo, y tiene exactamente $n - 1$ aristas.

Definición de DFS. Para un árbol con raíz fijo, un orden DFS se obtiene de la siguiente manera:

  • Todos los vértices están inicialmente no visitados.
  • Comienza en la raíz $1$, márcala como visitada y escríbela en la salida.
  • Cuando estés en algún vértice $v$, considera todos los hijos de $v$ en el árbol con raíz. Elige sus hijos en cualquier orden. Para cada hijo elegido $u$ que aún no haya sido visitado, ve a $u$, márcalo como visitado, escribe $u$ en la salida y continúa el DFS desde $u$ de la misma manera.

Para un árbol fijo, diferentes elecciones del orden en que se procesan los hijos de cada vértice pueden producir diferentes órdenes DFS. Todos los órdenes DFS son permutaciones de $1, 2, \dots, n$ y siempre comienzan con $1$.

Se te dan $m$ permutaciones de $1, 2, \dots, n$, cada una comenzando con $1$. Se te informa que cada una de ellas es un orden DFS del mismo árbol con raíz (con raíz $1$) en el sentido definido anteriormente (posiblemente utilizando diferentes elecciones de orden de los hijos en distintas ejecuciones del DFS).

Tu tarea es determinar cuántos árboles con raíz diferentes podrían producir todos estos $m$ órdenes DFS.

Dos árboles con raíz se consideran diferentes si sus conjuntos de aristas son diferentes.

Como la respuesta puede ser muy grande, debes imprimirla módulo $10^9 + 7$.

Entrada

La primera línea contiene dos enteros $n$ y $m$ ($1 \le n, m \le 500$).

Cada una de las siguientes $m$ líneas contiene una permutación $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ de los enteros $1, 2, \dots, n$, que describe el $k$-ésimo orden DFS.

Para todo $k$, todos los $p_{k,i}$ son distintos y $p_{k,1} = 1$.

Salida

Imprime un solo entero: el número de árboles con raíz con conjunto de vértices $1, 2, \dots, n$ y raíz $1$ para los cuales cada secuencia dada es un orden DFS válido de ese árbol, tomado módulo $10^9 + 7$.

Ejemplos

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.