# Verificador de HAMPATH

Un **camino hamiltoniano** de $s$ a $t$ en un grafo dirigido es un camino que empieza en $s$, termina en $t$ y
pasa por cada vértice del grafo exactamente una vez.

$$
\mathrm{HAMPATH} = \{\, \langle G, s, t \rangle : G \text{ es un grafo dirigido con un camino hamiltoniano de } s \text{ a } t \,\}
$$

Encontrar ese camino es difícil: no se conoce ningún algoritmo de tiempo polinomial. Comprobar uno que alguien
propone es fácil, y eso es lo que hace este programa. El certificado es una lista de vértices.

## Entrada

```text
n m
s t
u v          (m líneas: un arco de u a v)
c
k p1 p2 ... pk     (c líneas: un certificado por línea)
```

- El grafo tiene los vértices $1, 2, \ldots, n$ y $m$ arcos. Cada arco tiene dirección: `u v` es el arco de $u$
  a $v$, y no dice nada del arco de $v$ a $u$.
- Un mismo arco puede aparecer varias veces, y puede haber arcos de un vértice a sí mismo.
- Siguen $c$ certificados. Cada uno es un número $k$ y después $k$ enteros.

## Salida

Una línea por certificado, en el mismo orden: `válido` si la lista $p_1, \ldots, p_k$ es un camino hamiltoniano
de $s$ a $t$, e `inválido` si no. Es válida cuando cumple todo esto:

1. $k = n$.
2. Cada $p_i$ es un vértice: $1 \leq p_i \leq n$.
3. Ningún vértice se repite.
4. $p_1 = s$ y $p_k = t$.
5. Para cada $i$ de 1 a $k - 1$, el grafo tiene el arco de $p_i$ a $p_{i+1}$.

## Límites

- $1 \leq n \leq 200\,000$ y $0 \leq m \leq 500\,000$. $1 \leq s, t \leq n$, y puede ser $s = t$.
- $1 \leq c \leq 1000$.
- En cada certificado, $0 \leq k \leq 1\,000\,000$, y los $k$ de todos los certificados suman a lo sumo
  1 000 000.
- Los elementos de un certificado son enteros entre $-10^9$ y $10^9$: pueden no ser vértices.

## Ejemplo

Entrada (`casos/01.in`):

```text
5 8
1 5
1 2
2 3
3 4
4 5
1 3
3 2
2 4
5 1
7
5 1 2 3 4 5
5 1 3 2 4 5
4 1 3 4 5
5 1 2 2 4 5
5 1 2 3 4 6
5 1 2 4 3 5
5 2 3 4 5 1
```

Salida:

```text
válido
válido
inválido
inválido
inválido
inválido
inválido
```

Es el grafo del capítulo. Los dos primeros certificados son caminos hamiltonianos de 1 a 5. El tercero tiene 4
vértices, el cuarto repite el 2, el quinto nombra un vértice 6 que no existe y el sexto usa un arco de 4 a 3 que
no está. El último es un camino hamiltoniano, con todos sus arcos, pero va de 2 a 1 y no de $s$ a $t$.

## Tiempo

2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

Un camino de 200 000 vértices tiene 199 999 pasos, y por cada paso hay que saber si un arco existe. Si para eso
recorren la lista de los 500 000 arcos, son del orden de $10^{11}$ comparaciones y el juez da `TLE`. Tampoco sirve
una matriz de adyacencia: con $n = 200\,000$ tendría $4 \cdot 10^{10}$ casillas. Guarden los arcos de modo que la
pregunta "¿existe el arco de $u$ a $v$?" cueste poco: por ejemplo, ordenados y con búsqueda binaria, o las
listas de vecinos de cada vértice ordenadas. Un par $(u, v)$ cabe en un solo `long long` como
$u \cdot (n + 1) + v$, que llega a unos $4 \cdot 10^{10}$: no cabe en un `int`.

Hay una segunda manera de volver cuadrático el programa: buscar si un vértice se repite comparándolo con todos
los anteriores. Usen un arreglo indexado por el vértice.

## Casos de borde

Los casos pequeños traen, entre otros: un grafo de un solo vértice (el camino de un vértice es hamiltoniano, y no
usa ningún arco), un grafo sin arcos, $s = t$ con más de un vértice, arcos repetidos y arcos de un vértice a sí
mismo, un camino con todos sus arcos al revés, certificados vacíos ($k = 0$), certificados más largos que $n$, y
elementos que no son vértices: 0, negativos y mayores que $n$.

Antes de correr el juez, respondan a mano: si $s = t$ y $n \geq 2$, ¿puede algún certificado ser válido?

## Cómo avanzar

1. Lean la entrada completa y respondan `inválido` a todo. Con eso comprueban que leen bien: el juez debe dar
   `AC` en `casos/04.in` y `casos/05.in`, donde ningún certificado sirve.
2. Agreguen las condiciones una por una, en el orden de la lista de arriba. Las cuatro primeras no miran los
   arcos. Lean siempre los $k$ elementos, aunque ya sepan que el certificado es inválido.
3. Agreguen la condición de los arcos de la forma más simple y pasen los casos del 01 al 11.
4. Cambien la forma de guardar los arcos para pasar los casos 12 y 13, que `make test` genera con los programas
   `casos/gen_12.cpp` y `casos/gen_13.cpp`.
