Mihai, fiind un mare pasionat al jocurilor în aer liber, a inventat un joc nou în speranța că își va convinge colegii să iasă afară să se joace. Jocul lui Mihai spune că se dau N pătrate ce se află la anumite nivele iar din fiecare pătrat se poate sări doar în anumite pătrate stabilite la începutul jocului. Dacă un jucător sare dintr-un pătrat aflat la nivelul X într-un pătrat aflat la un nivel mai mare Y, acesta folosește un efort egal cu [Y/X], iar dacă sare într-un pătrat aflat la un nivel mai mic sau egal Y, efortul folosit este [X/Y]. Jucătorul se află la început în pătratul de start S și scopul jocului este să ajungă în pătratul final F, depunând un efort minim.

Cerința

Cunoscând numărul de pătrate N, pătratul de start S, pătratul final F și pentru fiecare pătrat, pătratele în care jucătorul poate sări, se cere:

a) Efortul minim necesar pentru a ajunge în pătratul final.

Mihai, fiind un mare pasionat al jocurilor în aer liber, a inventat un joc nou în speranța că își va convinge colegii să iasă afară să se joace. Jocul lui Mihai spune că se dau N pătrate ce se află la anumite nivele iar din fiecare pătrat se poate sări doar în anumite pătrate stabilite la începutul jocului. Dacă un jucător sare dintr-un pătrat aflat la nivelul X într-un pătrat aflat la un nivel mai mare Y, acesta folosește un efort egal cu [Y/X], iar dacă sare într-un pătrat aflat la un nivel mai mic sau egal Y, efortul folosit este [X/Y]. Jucătorul se află la început în pătratul de start S și scopul jocului este să ajungă în pătratul final F, depunând un efort minim.

Cerința

Cunoscând numărul de pătrate N, pătratul de start S, pătratul final F și pentru fiecare pătrat, pătratele în care jucătorul poate sări, se cere:

a) Efortul minim necesar pentru a ajunge în pătratul final.
b) Pătratele pe care jucătorul le sare până ajunge la pătratul final.

Date de intrare

Fişierul de intrare joc.in conține pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se află trei numere naturale N, S și F cu semnificația din enunț. Pe următoarea linie se află N numere naturale reprezentând nivelul la care se află fiecare pătrat. Pe următoarele N linii se află pătratele în care se poate sări din fiecare pătrat. Astfel, pe linia i se află numărul de pătrate în care se poate sări din pătratul i-3 urmat de pătratele în care se poate sări. Dacă dintr-un pătrat nu se poate sări în niciun alt pătrat atunci pe linia lui se află 0.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerintă. În acest caz, în fişierul de ieşire joc.out se va scrie un singur număr întreg reprezentând efortul minim necesar pentru a ajunge în pătratul final.

Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerintă. În acest caz, în fișierul de iesire joc.out se va scrie pe prima linie un număr natural M reprezentând numărul de pătrate necesare pentru a ajunge în pătratul final iar pe linia a doua se vor scrie cele M pătrate.

Restricții și precizări

• 1 ≤ S, F ≤ N ≤ 50 000
• S ≠ F
• numărul total al săriturilor stabilite la începutul jocului nu depăşeşte 500 000;
• nivelul maxim al unui pătrat ≤ 50 000;
• va exista întotdeauna o modalitate printr-un număr nenul de pași de a ajunge de la pătratul S la pătratul F;
• pentru rezolvarea corectă a primei cerinţe se acordă 40 de puncte, iar pentru cerința a doua se acordă 60 de puncte.

Exemplul 1:

joc.in

1
5 1 4
20 10 34 45 5
2 2 3
2 4 5
0
2 1 3
2 4 1

joc.out

6

Explicație

p = 1

Pentru a ajunge din primul pătrat adică pătratul aflat la nivelul 20 în cel de-al patrulea pătrat adică pătratul aflat la nivelul 45 cu un efort minim jucătorul sare de pe pătratul aflat la nivelul 20 pe pătratul aflat la nivelul 10 cu efortul 2 iar de pe pătratul aflat la nivelul 10 pe pătratul aflat la nivelul 45 cu efortul 4 obținând efortul 6.

Atenție! Pentru acest test se rezolvă doar cerința a).

Exemplul 2:

joc.in

2
5 1 4
20 10 34 45 5
2 2 3
2 4 5
0
2 1 3
2 4 1

joc.out

3
1 2 4

Explicație

p = 2

Pentru a ajunge din primul pătrat adică pătratul aflat la nivelul 20 în cel de-al patrulea pătrat adică pătratul aflat la nivelul 45 cu un efort minim jucătorul sare de pe pătratul aflat la nivelul 20 pe pătratul aflat la nivelul 10 iar de pe pătratul aflat la nivelul 10 pe pătratul aflat la nivelul 45.

Atenție! Pentru acest test se rezolvă doar cerința b).

#include <bits/stdc++.h>


using namespace std;

ifstream cin("joc.in");
ofstream cout("joc.out");
using VVP = vector <vector <pair<int , int> > >;
using VI = vector <int>;
using PI = pair<int , int>;
VI d;
VVP G;
const int Inf = 0x3f3f3f3f;
int cer , n , s , f , C[50001] , cate , x , T[50001] , cnt , rez[50001];

void Dijkstra(int x)
{
    d = VI(n + 1, Inf);
    priority_queue<PI, vector<PI>, greater<PI>> Q;
    int y , cost , dist;
    d[x] = 0;
    Q.push({0 , x});
    while(!Q.empty())
    {
        x = Q.top().second;
        dist = Q.top().first;
        Q.pop();
        if(dist > d[x]) continue;
        for(auto& p : G[x])
        {
            y = p.first;
            cost = p.second;
            if(d[y] > d[x] + cost)
            {
                d[y] = d[x] + cost;
                Q.push({d[y] , y});
                T[y] = x;
            }
        }
    }
}

int main()
{
    cin >> cer >> n >> s >> f;
    G = VVP(n + 1);
    for(int i = 1 ; i <= n ; i++)
        cin >> C[i];

    for(int i = 1 ; i <= n ; i++)
    {
        cin >> cate;
        for(int j = 1 ; j <= cate ; j++)
        {
            cin >> x;
            int cost = max(C[i] , C[x]) / min(C[i] , C[x]);
            G[i].push_back({x , cost});
        }
    }
    Dijkstra(s);
    if(cer == 1)cout << d[f];
    else
    {
        int poz = T[f];
        rez[++cnt] = f;
        while(poz != 0)
        {
            rez[++cnt] = poz;
            poz = T[poz];
        }
        cout << cnt << '\n';
        for(int i = cnt ; i >= 1 ; i--)
            cout << rez[i] << " ";
    }
}