// Wyznaczanie silnie spójnych składowych
// Data: 18.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

program scc;

// Typy dla dynamicznej tablicy
// list sąsiedztwa oraz stosu
type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------
Stack = object
  private
    // lista przechowująca stos
    S : PSLel;
  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push(v : integer);
    procedure  pop;
end;

// Konstruktor
//------------
constructor Stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------
destructor Stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function Stack.empty : boolean;
begin
  if S = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//-------------------------------
function Stack.top : integer;
begin
  if S <> nil then
    top := S^.v
  else
    top := -1;
end;

// Umieszcza dane na stosie
//-------------------------
procedure Stack.push(v : integer);
var
  e : PSLel;
begin
  new (e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure Stack.pop;
var
  e :PSLel;
begin
  if S <> NIL then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// Funkcja bada, czy istnieje
// ścieżka od u do v
// u - wierzchołek startowy ścieżki
// v - wierzchołek końcowy ścieżki
// n - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// Wynik:
// true - istnieje ścieżka od u do v
// false - nie istnieje ścieżka od u do v
//---------------------------------------
function DFSback(u, v, n : integer;
                 var graf : TList)
                          : boolean;
var
  i, x, y : integer;
  S : Stack;
  vs : array of boolean;
  p  : PSLel;
begin
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  // i wypełniamy ją wartościami false
  for i := 0 to n-1 do
    vs[i] := false;
  // Tworzymy stos
  S.init;
  // Wierzchołek startowy na stos
  S.push(u);
  // Oznaczamy go jako odwiedzonego
  vs[u] := true;
  // Uruchamiamy przejście DFS
  while not S.empty do
  begin
    // Pobieramy wierzchołek ze stosu
    x := S.top;
    // Pobrany wierzchołek usuwamy ze stosu
    S.pop;
    // Przeglądamy sąsiadów
    p := graf[x];
    while p <> nil do
    begin
      // Numer sąsiada do y
      y := p^.v;
      // Jeśli sąsiadem jest wierzchołek v,
      if y = v then
      // to ścieżka znaleziona
      begin
        // Zerujemy stos
        S.destroy;
        // Usuwamy tablicę vs
        SetLength(vs, 0);
        // Kończymy z wynikiem true
        Exit(true);
      end;
      if not vs[y] then
      begin
        // Nieodwiedzonego sąsiada
        // umieszczamy na stosie
        S.push(y);
        // i oznaczamy jako odwiedzonego
        vs[y] := true;
      end;
      // Następny sąsiad
      p := p^.next;
    end;
  end;
  // Usuwamy tablicę vs
  SetLength(vs, 0);
  // i kończymy z wynikiem false
  DFSback := false;
end;

// Procedura przechodzi przez graf
// od wierzchołka startowego v
// i umieszcza w tablicy C informację
// o przynależności wierzchołków
// do określonej silnie spójnej składowej
// v - wierzchołek startowy
// n - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// cn - numer silnie spójnej składowej
// C - tablica numerów silnie spójnych
//     składowych dla wierzchołków
// Wynik:
// Ustawia tablicę C
//----------------------------------------
procedure DFSscc (v, n : integer;
                  var graf : TList;
                  cn  : integer;
                  var C : array of integer);
var
  i, u, w : integer;
  S : Stack;
  vs : array of boolean;
  p : PSLel;
begin
  SetLength(vs, n);
  for i := 0 to n-1 do
    vs[i] := false;
  S.init;
  // Wierzchołek startowy na stos
  S.push(v);
  // Oznaczamy go jako odwiedzonego
  vs[v] := true;
  // Ustawiamy dla v numer składowej
  C[v] := cn;
  // Przejście DFS
  while not S.empty do
  begin
    // Odczytujemy wierzchołek ze stosu
    u := S.top;
    // Usuwamy ze stosu odczytany
    // wierzchołek
    S.pop;
    if(u <> v) and DFSback(u,v,n,graf) then
      C[u] := cn;
    // Przeglądamy sąsiadów wierzchołka u
    p := graf[u];
    while p <> nil do
    begin
      w := p^.v;
      if not vs [w] then
      begin
        // Nieodwiedzonego sąsiada
        // umieszczamy na stosie
        S.push(w);
        // i oznaczamy jako odwiedzonego
        vs[w] := true;
      end;
      // Następny sąsiad
      p := p^.next;
    end;
  end;
  SetLength(vs, 0);
end;

// **********************
// *** Program główny ***
// **********************

var
  // Liczba wierzchołków i krawędzi
  n, m : integer;
  // Tablica list sąsiedztwa grafu
  graf : TList;
  // Tablica numerów składowych
  C : array of integer;
  i, v, u, cn : integer;
  p, r : PSLel;

begin
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(graf, n);
  SetLength(C, n);
  // Inicjujemy tablice
  for i := 0 to n-1 do
  begin
    graf[i] := nil;
    C[i] := 0;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi.
  for i := 0 to m-1 do
  begin
    // Wierzchołki tworzące krawędź
    read(v, u);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako u
    p^.v := u;
    // i dodajemy na początek
    // listy graf[v]
    p^.next := graf[v];
    graf[v] := p;
  end;

  // Wyznaczamy silnie
  // spójne składowe
  //------------------
  // Inicjujemy licznik składowych
  cn := 0;
  // Przeglądamy kolejne
  // wierzchołki grafu
  for v := 0 to n-1 do
    if C[v] = 0 then
    begin
      inc(cn);
      // Wyznaczamy silnie
      // spójną składową
      DFSscc(v,n,graf,cn,C);
    end;
  // Wyświetlamy silnie
  // spójne składowe
  writeln;
  for i := 1 to cn do
  begin
    write('SCC', i:3, ' :');
    for v := 0 to n-1 do
      if C [v] = i then
        write(v:3);
    writeln;
  end;
  writeln;
  // Usuwamy tablice dynamiczne
  for i := 0 to n-1 do
  begin
    p := graf[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;
  SetLength(graf, 0);
  SetLength(C, 0);
end.

// Wyznaczanie silnie
// spójnych składowych
// Data: 18.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy
// list sąsiedztwa i stosu
struct SLel
{
  SLel * next;
  int v;
};

class Stack
{
  private:
    // lista przechowująca stos
    SLel * S;
  public:
    Stack(); // konstruktor
    ~Stack(); // destruktor
    bool empty(void);
    int  top(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu Stack
//---------------------

// Konstruktor
//------------
Stack::Stack()
{
  S = nullptr;
}

// Destruktor
//-----------
Stack::~Stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool Stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int Stack::top(void)
{
  if(S) return S->v;
  else return -1;
}

// Zapisuje na stos
//-----------------
void Stack::push(int v)
{
  SLel * e = new SLel;
  e->v = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void Stack::pop(void)
{
  if(S)
  {
    SLel * e = S;
    S = S->next;
    delete e;
  }
}

// Funkcja bada, czy istnieje
// ścieżka od u do v
// u - wierzchołek startowy ścieżki
// v - wierzchołek końcowy ścieżki
// n - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// Wynik:
// true - istnieje ścieżka od u do v
// false - nie istnieje ścieżka od u do v
//---------------------------------------
bool DFSback(int u, int v, int n,
             SLel ** graf)
{
  int i, x, y;
  Stack S;
  bool * vs;
  SLel * p;

  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  // i wypełniamy ją wartościami false
  for(i = 0; i < n; i++)
    vs[i] = false;
  // Wierzchołek startowy na stos
  S.push(u);
  // Oznaczamy go jako odwiedzonego
  vs[u] = true;
  // Uruchamiamy przejście DFS
  while(!S.empty())
  {
    // Pobieramy wierzchołek ze stosu
    x = S.top();
    // Pobrany wierzchołek
    // usuwamy ze stosu
    S.pop();
    // Przeglądamy sąsiadów
    for(p = graf[x]; p; p = p->next)
    {
      // Numer sąsiada do y
      y = p->v;
      // Jeśli sąsiadem jest
      // wierzchołek v,
      // to ścieżka znaleziona
      if(y == v)
      {
        // Usuwamy tablicę vs
        delete [] vs;
        // Kończymy z wynikiem true
        return true;
      }
      if(!vs[y])
      {
        // Nieodwiedzonego sąsiada
        // umieszczamy na stosie
        S.push(y);
        // i oznaczamy jako odwiedzonego
        vs[y] = true;
      }
    }
  }
  // Usuwamy tablicę vs
  delete [] vs;
  // i kończymy z wynikiem false
  return false;
}
// Procedura przechodzi przez graf
//  od wierzchołka startowego v
// i umieszcza w tablicy C informację
// o przynależności wierzchołków
// do określonej silnie spójnej składowej.
// v - wierzchołek startowy
// n - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// cn - numer silnie spójnej składowej
// C - tablica numerów silnie spójnych
// składowych dla wierzchołków
// Wynik:
// Ustawia tablicę C
//-----------------------------------------
void DFSscc(int v, int n,
            SLel ** graf,
            int cn, int * C)
{
  int i, u, w;
  Stack S;
  bool * vs;
  SLel * p;

  vs = new bool [n];
  for(i = 0; i < n; i++)
    vs[i] = false;
  // Wierzchołek startowy na stos
  S.push(v);
  // Oznaczamy go jako odwiedzonego
  vs[v] = true;
  // Ustawiamy dla v numer składowej
  C[v] = cn;
  // Przejście DFS
  while(!S.empty())
  {
    // Odczytujemy wierzchołek
    // ze stosu
    u = S.top();
    // Usuwamy ze stosu
    // odczytany wierzchołek
    S.pop();
    if((u != v) && DFSback(u,v,n,graf))
      C[u] = cn;
    // Przeglądamy sąsiadów
    // wierzchołka u
    for(p = graf[u]; p; p = p->next)
    {
      w = p->v;
      if(!vs[w])
      {
        // Nieodwiedzonego sąsiada
        // umieszczamy na stosie
        S.push(w);
        // i oznaczamy jako odwiedzonego
        vs[w] = true;
      }
    }
  }
  delete [] vs;
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  // Liczba wierzchołków i krawędzi
  int n, m;
  // Tablica list sąsiedztwa
  SLel ** graf;
  // Tablica z numerami
  // spójnych składowych
  int * C;
  int i, v, u, cn;
  SLel *p, *r;

  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablice dynamiczne
  graf = new SLel * [n];
  C = new int [n];
  // Inicjujemy tablice
  for(i = 0; i < n; i++)
  {
    graf[i] = nullptr;
    C[i] = 0;
  }
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołki tworzące krawędź
    cin >> v >> u;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako u
    p->v = u;
    // Dodajemy go na początek
    // listy graf[v]
    p->next = graf[v];
    graf[v] = p;
  }
  // Wyznaczamy silnie spójne składowe
  //----------------------------------
  // Inicjujemy licznik składowych
  cn = 0;
  // Przeglądamy kolejne
  // wierzchołki grafu
  for(v = 0; v <= n-1; v++)
    // Wyznaczamy silnie
    // spójną składową
    if(!C[v]) DFSscc(v,n,graf,++cn,C);
  // Wyświetlamy silnie spójne składowe
  cout << endl;
  for(i = 1; i <= cn; i++)
  {
    cout << "SCC" << setw(3) << i << ":";
    for(v = 0; v < n; v++)
      if(C[v] == i) cout << setw(3) << v;
    cout << endl;
  }
  cout << endl;
  // Usuwamy tablice dynamiczne
  for(i = 0; i < n; i++)
  {
    p = graf[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] graf;
  delete [] C;
  return 0;
}

' Wyznaczanie silnie spójnych składowych
' Data: 18.01.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------------------

' Typy dla dynamicznej tablicy
' list sąsiedztwa i stosu
Type SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    ' lista zawierająca stos
    S As SLel Ptr
  Public:
    Declare Constructor
    Declare Destructor
    Declare Function empty As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop
End Type

'---------------------
' Metody obiektu Stack
'---------------------

' Konstruktor
'------------
Constructor Stack
  S = 0
End Constructor

' Destruktor
'-----------
Destructor Stack
  While S
    pop()
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function Stack.empty As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu
'--------------------
Function Stack.top As Integer
  If S = 0 Then
    top = -1
  Else
    top = S->v
  End If
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push(ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v = v
  e->next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop
  Dim e As SLel Ptr
  If S Then
    e = S
    S = S->Next
    Delete e
  End If
End Sub

' Funkcja bada, czy istnieje ścieżka
' od u do v
' u - wierzchołek startowy ścieżki
' v - wierzchołek końcowy ścieżki
' n - liczba wierzchołków w grafie
' graf - tablica list sąsiedztwa
' Wynik:
' 1 - istnieje ścieżka od u do v
' 0 - nie istnieje ścieżka od u do v
'-----------------------------------
Function DFSback(ByVal u As Integer, _
                 ByVal v As integer, _
                 ByVal n As integer, _
                 ByVal graf As SLel Ptr Ptr)_
                            As Integer
  Dim As integer i, x, y
  Dim As Stack S
  Dim As Byte Ptr vs
  Dim As SLel Ptr  p

  ' Tworzymy tablicę odwiedzin
  vs = New Byte [n]
  ' i wypełniamy ją wartościami false
  For i = 0 To n-1
    vs[i] = 0
  Next
  ' Wierzchołek startowy na stos
  S.push(u)
  ' Oznaczamy go jako odwiedzonego
  vs[u] = 1
  ' Uruchamiamy przejście DFS
  While S.empty = 0
    ' Pobieramy wierzchołek ze stosu
    x = S.top
    ' Pobrany wierzchołek usuwamy ze stosu
    S.pop
    p = graf[x]
    ' Przeglądamy sąsiadów
    While p
      ' Numer sąsiada do y
      y = p->v
      ' Jeśli sąsiadem jest wierzchołek v,
      ' to ścieżka znaleziona
      If y = v Then
        ' Usuwamy tablicę vs
        Delete [] vs
        ' Kończymy z wynikiem true
        Return 1
      End If
      If vs[y] = 0 Then
        ' Nieodwiedzonego sąsiada
        ' umieszczamy na stosie
        S.push(y)
        ' i oznaczamy jako odwiedzonego
        vs[y] = 1
      End If
      ' Następny sąsiad
      p = p->next
    Wend
  Wend
  ' Usuwamy tablicę vs
  Delete [] vs
  ' i kończymy z wynikiem false
  Return 0
End Function

' Procedura przechodzi przez graf
' od wierzchołka startowego v
' i umieszcza w tablicy C informację
' o przynależności wierzchołków
' do określonej silnie spójnej składowej.
' v - wierzchołek startowy
' n - liczba wierzchołków w grafie
' graf - tablica list sąsiedztwa
' cn - numer silnie spójnej składowej
' C - tablica numerów silnie spójnych
'     składowych dla wierzchołków
' Wynik:
' Ustawia tablicę C
'--------------------------------------
Sub DFSscc(ByVal v As integer, _
           ByVal n As integer, _
           ByVal graf As SLel Ptr ptr, _
           ByVal cn As integer, _
           ByVal C As Integer Ptr)
  Dim As Integer i, u, w
  Dim As Stack S
  Dim As Byte Ptr vs
  Dim As SLel Ptr p

  vs = New Byte [n]
  For i = 0 To n-1
    vs[i] = 0
  Next
  ' Wierzchołek startowy na stos
  S.push(v)
  ' Oznaczamy go jako odwiedzonego
  vs[v] = 1
  ' Ustawiamy dla v numer składowej
  C[v] = cn
  ' Przejście DFS
  While S.empty = 0
    ' Odczytujemy wierzchołek ze stosu
    u = S.top
    ' Usuwamy ze stosu odczytany wierzchołek
    S.pop
    If (u <> v) AndAlso _
       (DFSback(u,v,n,graf) = 1) Then _
      C[u] = cn                 
    p = graf[u]
    ' Przeglądamy sąsiadów wierzchołka u
    While p
      w = p->v
      If vs[w] = 0 Then
        ' Nieodwiedzonego sąsiada
        ' umieszczamy na stosie
        S.push(w)
        ' i oznaczamy jako odwiedzonego
        vs[w] = 1
      End If
      p = p->Next
    Wend
  Wend
  Delete [] vs
End Sub

' **********************
' *** Program główny ***
' **********************

' Liczba wierzchołków i krawędzi
Dim As Integer n, m
' Tablica list sąsiedztwa grafu
Dim As SLel Ptr Ptr graf
Dim As Integer Ptr C
Dim As Integer i, v, u, cn
Dim As SLel Ptr p, r

Open Cons For Input As #1
' Odczytujemy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
graf = New SLel Ptr [n]
C = New Integer [n]
' Inicjujemy tablice
For i = 0 To n-1
  graf[i] = 0
  C[i] = 0
Next
' Odczytujemy kolejne definicje krawędzi.
For i = 1 To m
  ' Wierzchołki tworzące krawędź
  Input #1, v, u
  ' Tworzymy nowy element
  p = New SLel
  ' Numerujemy go jako u
  p->v = u
  ' Dodajemy go na początek listy graf[v]
  p->next = graf[v]
  graf[v] = p
Next
Close #1
' Wyznaczamy silnie spójne składowe
'----------------------------------
' Inicjujemy licznik składowych
cn = 0
' Przeglądamy kolejne wierzchołki grafu
For v = 0 To n-1
  If C[v] = 0 Then
  	  cn += 1
  	  ' Wyznaczamy silnie spójną składową
      DFSscc(v,n,graf,cn,C)
  End If
Next
' Wyświetlamy silnie spójne składowe
Print
For i = 1 To cn
  Print Using "SCC### :"; i;
  For v = 0 To n-1
    If C[v] = i Then Print Using "###";v;
  Next
  Print
Next
Print
' Usuwamy tablice dynamiczne
For i = 0 To n-1
  p = graf[i]
  While p
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] graf
Delete [] C
End

# Wyznaczanie silnie spójnych składowych
# Data: 3.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------------------

# Klasy dla dynamicznej tablicy
# list sąsiedztwa i stosu
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


class Stack:
    # Konstruktor
    def __init__(self):
        self.s = None

    # Destruktor
    def __del__(self):
        while self.s:
            self.pop()


    # Sprawdza, czy stos jest pusty
    def empty(self):
        return not self.s


    # Zwraca szczyt stosu
    def top(self):
        if self.s:
            return self.s.v
        else:
            return -1


    # Zapisuje na stos
    def push(self, v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# Funkcja bada, czy istnieje ścieżka
# od u do v
# u - wierzchołek startowy ścieżki
# v - wierzchołek końcowy ścieżki
# n - liczba wierzchołków w grafie
# graf - tablica list sąsiedztwa
# Wynik:
# 1 - istnieje ścieżka od u do v
# 0 - nie istnieje ścieżka od u do v
#-----------------------------------
def dfs_back(u, v, n, graf):
    s = Stack()
    # Tworzymy tablicę odwiedzin
    vs = [False] * n
    # Wierzchołek startowy na stos
    s.push(u)
    # Oznaczamy go jako odwiedzonego
    vs[u] = True
    # Uruchamiamy przejście DFS
    while not s.empty():
        # Pobieramy wierzchołek ze stosu
        x = s.top()
        # Pobrany wierzchołek usuwamy
        # ze stosu
        s.pop()
        p = graf[x]
        # Przeglądamy sąsiadów
        while p:
            # Numer sąsiada do y
            y = p.v
            # Jeśli sąsiadem jest
            # wierzchołek v, to ścieżka 
            # jest znaleziona
            if y == v:
                # Usuwamy tablicę vs
                del vs
                # Kończymy z wynikiem true
                return True
            if not vs[y]:
                # Nieodwiedzonego sąsiada
                # umieszczamy na stosie
                s.push(y)
                # i oznaczamy jako
                # odwiedzonego
                vs[y] = True
            # Następny sąsiad
            p = p.next
    # Usuwamy tablicę vs
    del vs
    # i kończymy z wynikiem false
    return False

# Procedura przechodzi przez graf
# od wierzchołka startowego v
# i umieszcza w tablicy C informację
# o przynależności wierzchołków
# do określonej silnie spójnej składowej.
# v - wierzchołek startowy
# n - liczba wierzchołków w grafie
# graf - tablica list sąsiedztwa
# cn - numer silnie spójnej składowej
# c - tablica numerów silnie spójnych
#     składowych dla wierzchołków
# Wynik:
# Ustawia tablicę C
#--------------------------------------
def dfs_scc(v, n, graf, cn, c):
    s = Stack()
    vs = [False] * n
    # Wierzchołek startowy na stos
    s.push(v)
    # Oznaczamy go jako odwiedzonego
    vs[v] = 1
    # Ustawiamy dla v numer składowej
    c[v] = cn
    # Przejście DFS
    while not s.empty():
        # Odczytujemy wierzchołek ze stosu
        u = s.top()
        # Usuwamy ze stosu odczytany
        # wierzchołek
        s.pop()
        if (u != v) and dfs_back(u,v,n,graf):
            c[u] = cn
        p = graf[u]
        # Przeglądamy sąsiadów wierzchołka u
        while p:
            w = p.v
            if not vs[w]:
                # Nieodwiedzonego sąsiada
                # umieszczamy na stosie
                s.push(w)
                # i oznaczamy jako
                # odwiedzonego
                vs[w] = True
            p = p.next
    del vs


# **********************
# *** Program główny ***
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
graf = [None] * n
c = [0] * n
# Odczytujemy kolejne definicje krawędzi.
for i in range(m):
    # Wierzchołki tworzące krawędź
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako u
    p.v = u
    # Dodajemy go na początek listy graf[v]
    p.next = graf[v]
    graf[v] = p
# Wyznaczamy silnie spójne składowe
#----------------------------------
# Inicjujemy licznik składowych
cn = 0
# Przeglądamy kolejne wierzchołki grafu
for v in range(n):
    if not c[v]:
        cn += 1
        # Wyznaczamy silnie spójną składową
        dfs_scc(v,n,graf,cn,c)
# Wyświetlamy silnie spójne składowe
print()
for i in range(1,cn+1):
    print("SCC%3d:" % i, end="")
    for v in range(n):
        if c[v] == i:
            print("%3d" % v, end="")
    print()
print()
# Usuwamy tablice dynamiczne
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del graf, c

// Wyznaczanie silnie
// spójnych składowych
// Algorytm Korsaraju
// Data: 26.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program scc;

// Typy dla dynamicznej tablicy
// list sąsiedztwa oraz stosu
type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

  TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------
Stack = object
  private
    // lista przechowująca stos
    S : PSLel;
  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push(v : integer);
    procedure  pop;
end;

// Konstruktor
//------------
constructor Stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------
destructor Stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function Stack.empty : boolean;
begin
  if S = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//-------------------------------
function Stack.top : integer;
begin
  if empty = true then
    top := -1
  else
    top := S^.v;
end;

// Umieszcza dane na stosie
//-------------------------
procedure Stack.push(v : integer);
var
  e : PSLel;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure Stack.pop;
var
  e : PSLel;
begin
  if S <> NIL then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// Przechodzi graf algorytmem DFS,
// umieszczając na stosie
// napotkane po drodze wierzchołki.
// v - numer wierzchołka startowego
// vs - tablica odwiedzin
// S - stos
// graf - tablica list sąsiedztwa
//---------------------------------
procedure DFSStack(v : integer;
         var vs : array of boolean;
               var S : Stack;
            var graf : TList);
var
  p : PSLel;
begin
  // Oznaczamy v jako odwiedzony
  vs[v] := true;
  // Przeglądamy sąsiadów v
  p := graf[v];
  while p <> nil do
  begin
    if not vs[p^.v] then
      DFSStack(p^.v, vs, S, graf);
    p := p^.next;
  end;
  S.push (v);
end;

// Wyświetla wierzchołki kolejno
// odwiedzane przez DFS
// v - wierzchołek startowy
// vs - tablica odwiedzin
// graf - tablica list sąsiedztwa
//-------------------------------
procedure DFSprint(v : integer;
         var vs : array of boolean;
            var graf : TList);
var
  p : PSLel;
begin
  vs[v] := true;
  write(v:3);
  p := graf[v];
  while p <> nil do
  begin
    if not vs[p^.v] then
      DFSprint(p^.v, vs, graf);
    p := p^.next;
  end;
end;

// **********************
// *** Program główny ***
// **********************

var
  // Liczba wierzchołków i krawędzi
  n, m : integer;
  // Tablice list sąsiedztwa
  A, AT : TList;
  vs  : array of boolean;
  S : Stack;
  i, v, u, cn : integer;
  p, r : PSLel;

begin
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(A, n);
  SetLength(AT, n);
  // Inicjujemy tablice
  for i := 0 to n-1 do
  begin
    A[i] := nil;
    AT[i] := nil;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi.
  for i := 0 to m-1 do
  begin
    // Wierzchołki tworzące krawędź
    read(v, u);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako u
    p^.v := u;
    // i dodajemy na początek
    // listy A[v]
    p^.next := A[v];
    A[v] := p;
  end;
  writeln;
  // Wyznaczamy silnie spójne składowe
  //----------------------------------
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  // i wypełniamy ją wartościami false
  for i := 0 to n-1 do
    vs[i] := false;
  // Tworzymy pusty stos
  S.init;
  // Przeglądamy kolejne
  // wierzchołki grafu
  for v := 0 to n-1 do
    if not vs[v] then
      DFSStack(v, vs, S, A);
  // Transponujemy graf
  //-------------------
  // Przeglądamy kolejne wierzchołki
  for v := 0 to n-1 do
  begin
    // Przeglądamy sąsiadów v
    p := A[v];
    while p <> nil do
    begin
      // Tworzymy nowy element listy
      new(r);
      // Zapamiętujemy w nim wierzchołek v
      r^.v := v;
      // i dodajemy do listy sąsiada
      r^.next := AT[p^.v];
      AT[p^.v] := r;
      // Następny sąsiad
      p := p^.next;
    end;
  end;
  // Zerujemy tablicę odwiedzin
  for v := 0 to n-1 do
    vs[v] := false;
  // Inicjujemy licznik składowych
  cn := 0;
  // Przetwarzamy wierzchołki ze stosu
  while not S.empty do
  begin
    // Pobieramy wierzchołek ze stosu
    v := S.top; S.pop;
    if not vs[v] then
    begin
      // Zwiększamy licznik składowych
      inc(cn);
      write('SCC', cn:3, ' :');
      DFSprint(v, vs, AT);
      writeln;
    end;
  end;
  // Usuwamy tablice dynamiczne
  for i := 0 to n-1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
    p := AT[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;
  SetLength(A, 0);
  SetLength(AT, 0);
  SetLength(vs, 0);
  S.destroy;
end.

// Wyznaczanie silnie
// spójnych składowych
// Algorytm Korsaraju
// Data: 26.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy
// list sąsiedztwa i stosu
struct SLel
{
  SLel * next;
  int v;
};

class Stack
{
  private:
    // lista przechowująca stos
    SLel * S;

  public:
    Stack(); // konstruktor
    ~Stack(); // destruktor
    bool empty(void);
    int  top(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu Stack
//---------------------

// Konstruktor
//------------
Stack::Stack()
{
  S = nullptr;
}

// Destruktor
//-----------
Stack::~Stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool Stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int Stack::top(void)
{
  if(S) return S->v;
  else return -1;
}

// Zapisuje na stos
//-----------------
void Stack::push(int v)
{
  SLel * e = new SLel;
  e->v = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void Stack::pop(void)
{
  if(S)
  {
    SLel * e = S;
    S = S->next;
    delete e;
  }
}

// Przechodzi graf algorytmem DFS,
// umieszczając na stosie
// napotkane po drodze wierzchołki.
// v - numer wierzchołka startowego
// vs - tablica odwiedzin
// S - stos
// graf - tablica list sąsiedztwa
//---------------------------------
void DFSStack(int v,
              bool * vs,
              Stack & S,
              SLel ** graf)
{
  SLel * p;

  // Oznaczamy v jako odwiedzony
  vs[v] = true;
  // Przeglądamy sąsiadów v
  for(p = graf[v]; p; p = p->next)
    if(!vs[p->v])
      DFSStack(p->v, vs, S, graf);
  S.push(v);
}

// Wyświetla wierzchołki kolejno
// odwiedzane przez DFS
// v - wierzchołek startowy
// vs - tablica odwiedzin
// graf - tablica list sąsiedztwa
//-------------------------------
void DFSprint(int v,
              bool * vs,
              SLel ** graf)
{
  SLel * p;

  vs[v] = true;
  cout << setw(3) << v;
  for(p = graf[v]; p; p = p->next)
    if(!vs[p->v])
      DFSprint(p->v, vs, graf);
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  // Liczba wierzchołków i krawędzi
  int n, m;
  // Tablice list sąsiedztwa
  SLel **A, **AT;
  bool * vs;
  Stack S;
  int i, v, u, cn;
  SLel *p, *r;

  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablice dynamiczne
  A  = new SLel * [n];
  AT = new SLel * [n];
  // Inicjujemy tablice
  for(i = 0; i < n; i++)
    A[i] = AT[i] = nullptr;
  // Odczytujemy kolejne
  // definicje krawędzi.
  for(i = 0; i < m; i++)
  {
    // Wierzchołki tworzące krawędź
    cin >> v >> u;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako u
    p->v = u;
    // i dodajemy na początek
    // listy A[v]
    p->next = A[v];
    A[v] = p;
  }
  cout << endl;
  // Wyznaczamy silnie spójne składowe
  //----------------------------------
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  // i wypełniamy ją wartościami false
  for(i = 0; i < n; i++)
    vs[i] = false;
  // Przeglądamy kolejne
  // wierzchołki grafu
  for(v = 0; v < n; v++)
    if(!vs[v])
      DFSStack(v, vs, S, A);
  // Transponujemy graf
  //-------------------
  // Przeglądamy kolejne wierzchołki
  for(v = 0; v < n; v++)
    // Przeglądamy sąsiadów v
    for(p = A[v]; p; p = p->next)
    {
      // Tworzymy nowy element listy
      r = new SLel;
      // Zapamiętujemy w nim
      // wierzchołek v
      r->v = v;
      // i dodajemy do listy sąsiada
      r->next = AT[p->v];
      AT[p->v] = r;
    }
  // Zerujemy tablicę odwiedzin
  for(v = 0; v < n; v++)
    vs[v] = false;
  // Inicjujemy licznik składowych
  cn = 0;
  // Przetwarzamy wierzchołki
  // ze stosu
  while(!S.empty())
  {
    // Pobieramy wierzchołek ze stosu
    v = S.top(); S.pop();
    if(!vs [v])
    {
      cout << "SCC" << setw(3)
           << ++cn << ":";
      DFSprint(v, vs, AT);
      cout << endl;
    }
  }
  // Usuwamy tablice dynamiczne
  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
    p = AT[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  delete [] AT;
  delete [] vs;
  return 0;
}

' Wyznaczanie silnie spójnych składowych
' Algorytm Korsaraju
' Data: 25.01.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------------------

' Typy dla dynamicznej tablicy
' list sąsiedztwa i stosu
Type SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    ' lista zawierająca stos
    S As SLel Ptr
  Public:
    Declare Constructor
    Declare Destructor
    Declare Function empty As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop
End Type

'---------------------
' Metody obiektu Stack
'---------------------

' Konstruktor
'------------
Constructor Stack
  S = 0
End Constructor

' Destruktor
'-----------
Destructor Stack
  While S
    pop
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function Stack.empty As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function Stack.top As Integer
  If S = 0 Then
    top = -1
  Else
    top = S->v
  End If
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push(ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v = v
  e->next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop
  Dim e As SLel Ptr
  If S Then
    e = S
    S = S->Next
    Delete e
  End If
End Sub

' Przechodzi graf algorytmem DFS,
' umieszczając na stosie
' napotkane po drodze wierzchołki.
' v - numer wierzchołka startowego
' vs - tablica odwiedzin
' S - stos
' graf - tablica list sąsiedztwa
'---------------------------------
Sub DFSStack(ByVal v As integer, _
             ByVal vs As Byte Ptr, _
             ByRef S As Stack, _
             ByVal graf As SLel Ptr Ptr)
  Dim As SLel Ptr p

  ' Oznaczamy v jako odwiedzony
  vs[v] = 1
  ' Przeglądamy sąsiadów v
  p = graf[v]
  While p
    If vs[p->v] = 0 Then _
      DFSStack(p->v, vs, S, graf)
    p = p->next
  Wend
  S.push(v)
End Sub

' Wyświetla wierzchołki kolejno
' odwiedzane przez DFS
' v - wierzchołek startowy
' vs - tablica odwiedzin
' graf - tablica list sąsiedztwa
'-------------------------------
Sub DFSprint(ByVal v As integer, _
             ByVal vs As Byte ptr, _
             ByVal graf As SLel Ptr Ptr)
  Dim As SLel Ptr p

  vs[v] = 1
  Print Using "###";v;
  p = graf[v]
  While p <> 0
    If vs[p->v] = 0 Then _
      DFSprint(p->v, vs, graf)
    p = p->next
  Wend
End Sub

' **********************
' *** Program główny ***
' **********************

' Liczba wierzchołków i krawędzi
Dim As Integer n, m
' Tablice list sąsiedztwa
Dim As SLel Ptr Ptr A, AT
Dim As Byte Ptr vs
Dim As Stack S
Dim As Integer i, v, u, cn
Dim As SLel Ptr p, r

Open Cons For Input As #1
' Odczytujemy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
A  = New SLel Ptr [n]
AT = New SLel Ptr [n]
' Inicjujemy tablice
For i = 0 To n-1
  A[i]  = 0
  AT[i] = 0
Next
' Odczytujemy kolejne definicje krawędzi.
For i = 1 To m
  ' Wierzchołki tworzące krawędź
  Input #1, v, u
  ' Tworzymy nowy element
  p = New SLel
  ' Numerujemy go jako u
  p->v = u
  ' Dodajemy go na początek listy A[v]
  p->next = A[v]
  A[v] = p
Next
Close #1
Print
' Wyznaczamy silnie spójne składowe
'----------------------------------
' Tworzymy tablicę odwiedzin
vs = New Byte [n]
' i wypełniamy ją wartościami false
For i = 0 To n-1
  vs[i] = 0
Next
' Przeglądamy kolejne wierzchołki grafu
For v = 0 To n-1
  If vs[v] = 0 Then _
      DFSStack(v, vs, S, A)
Next
' Transponujemy graf
'-------------------
' Przeglądamy kolejne wierzchołki
For v = 0 To n-1
  ' Przeglądamy sąsiadów v
  p = A[v]
  While p
    ' Tworzymy nowy element listy
    r = New SLel
    ' Zapamiętujemy w nim wierzchołek v
    r->v = v
    ' i dodajemy do listy sąsiada
    r->next = AT[p->v]
    AT[p->v] = r
    p = p->Next
  Wend
Next
' Zerujemy tablicę odwiedzin
For v = 0 To n-1
  vs[v] = 0
Next
' Inicjujemy licznik składowych
cn = 0
' Przetwarzamy wierzchołki ze stosu
While S.empty = 0
  ' Pobieramy wierzchołek ze stosu
  v = S.top: S.pop
  If vs[v] = 0 Then
    cn += 1
    Print Using "SCC### :";cn;
    DFSprint(v, vs, AT)
    Print
  End If
Wend
' Usuwamy tablice dynamiczne
For i = 0 To n-1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
  p = AT[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [] A
Delete [] AT
Delete [] vs
End

# Wyznaczanie silnie spójnych składowych
# Algorytm Korsaraju
# Data: 25.01.2014
# (C)2014 mgr Jerzy Wałaszek
#---------------------------------------

# Klasy dla dynamicznej tablicy
# list sąsiedztwa i stosu
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


class Stack:
    # Konstruktor
    def __init__(self):
        # lista zawierająca stos
        self.s = None

    # Destruktor
    def __del__(self):
        while self.s:
            self.pop()


    # Sprawdza, czy stos jest pusty
    def empty(self):
        return not self.s


    # Zwraca szczyt stosu.
    def top(self):
        if not self.s:
            return -1
        else:
            return self.s.v


    # Zapisuje na stos
    def push(self, v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# Przechodzi graf algorytmem DFS,
# umieszczając na stosie
# napotkane po drodze wierzchołki.
# v - numer wierzchołka startowego
# vs - tablica odwiedzin
# S - stos
# graf - tablica list sąsiedztwa
def dfs_stack(v, vs, s, graf):
    # Oznaczamy v jako odwiedzony
    vs[v] = True
    # Przeglądamy sąsiadów v
    p = graf[v]
    while p:
        if not vs[p.v]:
            dfs_stack(p.v, vs, s, graf)
        p = p.next
    s.push(v)


# Wyświetla wierzchołki kolejno
# odwiedzane przez DFS
# v - wierzchołek startowy
# vs - tablica odwiedzin
# graf - tablica list sąsiedztwa
def dfs_print(v, vs, graf):
    vs[v] = True
    print("%3d" % v, end="")
    p = graf[v]
    while p:
        if not vs[p.v]:
            dfs_print(p.v, vs, graf)
        p = p.next


# **********************
# *** Program główny ***
# **********************

s = Stack()

# Odczytujemy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
a = [None] * n
at = [None] * n
# Odczytujemy kolejne definicje krawędzi.
for i in range(m):
    # Wierzchołki tworzące krawędź
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako u
    p.v = u
    # Dodajemy go na początek listy A[v]
    p.next = a[v]
    a[v] = p
print()
# Wyznaczamy silnie spójne składowe
#----------------------------------
# Tworzymy tablicę odwiedzin
vs = [False] * n
# Przeglądamy kolejne wierzchołki grafu
for v in range(n):
    if not vs[v]:
        dfs_stack(v, vs, s, a)
# Transponujemy graf
#-------------------
# Przeglądamy kolejne wierzchołki
for v in range(n):
    # Przeglądamy sąsiadów v
    p = a[v]
    while p:
        # Tworzymy nowy element listy
        r = SLel()
        # Zapamiętujemy w nim wierzchołek v
        r.v = v
        # i dodajemy do listy sąsiada
        r.next = at[p.v]
        at[p.v] = r
        p = p.next
# Zerujemy tablicę odwiedzin
for v in range(n):
    vs[v] = False
# Inicjujemy licznik składowych
cn = 0
# Przetwarzamy wierzchołki ze stosu
while not s.empty():
    # Pobieramy wierzchołek ze stosu
    v = s.top()
    s.pop()
    if not vs[v]:
        cn += 1
        print("SCC%3d :" % cn, end="")
        dfs_print(v, vs, at)
        print()
# Usuwamy tablice dynamiczne
for i in range(n):
    while a[i]:
        a[i] = a[i].next
    while at[i]:
        at[i] = at[i].next
del a, at, vs

// Wyznaczanie silnie
// spójnych składowych
// Algorytm Tarjana
// Data: 2.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program scc;

// Typy danych
type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

// Typ danych dla listy
// silnie spójnych składowych
//---------------------------
  PsSLel = ^sSLel;
  sSLel = record
    next : PsSLel;
    v    : PSLel;
  end;

// Definicja typu
// obiektowego Stack
//------------------
  Stack = object
    private
      // lista przechowująca stos
      S : PSLel;

    public
      constructor init;
      destructor destroy;
      function   empty : boolean;
      function   top : integer;
      procedure  push(v : integer);
      procedure  pop;
  end;

// Zmienne globalne
//-----------------
var
  n, m, cvn : integer;
  VN, VLow : array of integer;
  VS : array of boolean;
  S  : Stack;
  graf : array of PSLel;
  Lscc : PsSLel;

// Metody klasy Stack
//-------------------
// Konstruktor
//------------
constructor Stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------
destructor Stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function Stack.empty : boolean;
begin
  if S = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//-------------------------------
function Stack.top : integer;
begin
  if S <> nil then
    top := S^.v
  else
    top := -1;
end;

// Umieszcza dane na stosie
//-------------------------
procedure Stack.push(v : integer);
var
  e : PSLel;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure Stack.pop;
var
  e :PSLel;
begin
  if S <> nil then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// Zwraca mniejszą z dwóch liczb
//------------------------------
function min(a, b : integer)
                  : integer;
begin
  if a < b then
    min := a
  else
    min := b;
end;

// Procedura wykonująca
// przejście DFS
// i wyznaczająca
// silnie spójną składową.
// v - wierzchołek startowy dla DFS
//---------------------------------
procedure DFSscc(v : integer);
var
  u : integer;
  sccp, p : PSLel;
  listp : PsSLel;
begin
  // Zwiększamy numer wierzchołka
  inc(cvn);
  // Numerujemy bieżący wierzchołek
  VN[v] := cvn;
  // Ustalamy wstępnie parametr Low
  VLow[v] := cvn;
  // Wierzchołek na stos
  S.push(v);
  // Zapamiętujemy,
  // iż v jest na stosie
  VS[v] := true;
  // Przeglądamy listę sąsiadów
  p := graf[v];
  while p <> nil do
  begin
    // Jeśli sąsiad jest
    // nieodwiedzony, to
    if VN[p^.v] = 0 then
    begin
      // wywołujemy dla niego
      // rekurencyjnie DFS
      DFSscc(p^.v);
      // i obliczamy parametr Low dla v
      VLow[v] := min(VLow[v],VLow[p^.v]);
    end
    // Jeśli sąsiad odwiedzony,
    // lecz wciąż na stosie,
    else if VS[p^.v] then
      // to wyznaczamy parametr Low dla v
    VLow[v] := min(VLow[v],VN[p^.v]);
    p := p^.next;
  end;
  // Sprawdzamy, czy mamy
  // kompletną składową
  if VLow[v] = VN[v] then
  begin
    // Dodajemy tę składową do
    // listy składowych
    sccp := nil;
    repeat
      // Pobieramy wierzchołek
      // ze stosu
      u := S.top;
      // Pobrany wierzchołek
      // usuwamy ze stosu
      S.pop;
      // Zapamiętujemy, że nie ma
      // go już na stosie
      VS[u] := false;
      // Nowy element
      // listy wierzchołków
      new(p);
      // Zapisujemy w nim wierzchołek
      p^.v := u;
      // dodajemy go na początek listy
      p^.next := sccp;
      sccp := p;
    // Kontynuujemy aż do
    // korzenia składowej
    until u = v;
    // Nowy element listy składowych
    new(listp);
    // Zapisujemy w nim listę
    listp^.v := sccp;
    // i dołączamy na początek
    // listy składowych
    listp^.next := Lscc;
    Lscc := listp;
  end;
end;

// **********************
// *** Program główny ***
// **********************

var
  i, v, u : integer;
  p, r : PSLel;
  listp, listr : PsSLel;

begin
  // Tworzymy pusty stos
  S.init;
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(graf, n);
  SetLength(VN, n);
  SetLength(VLow, n);
  SetLength(VS, n);
  // Inicjujemy tablice
  for i := 0 to n-1 do
  begin
    graf[i] := nil;
    VN[i]   := 0;
    VS[i]   := false;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi.
  for i := 0 to m-1 do
  begin
    // Wierzchołki tworzące krawędź
    read(v, u);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako u
    p^.v := u;
    // i dodajemy na początek
    // listy graf[v]
    p^.next := graf[v];
    graf[v] := p;
  end;
  writeln;
  // Wyznaczamy silnie spójne składowe
  //----------------------------------
  // Zerujemy numer wierzchołka
  cvn := 0;
  // Tworzymy pustą listę składowych
  Lscc := nil;
  // Przeglądamy kolejne wierzchołki
  for v := 0 to n-1 do
    // W wierzchołku nieodwiedzonym
    // uruchamiamy DFS
    if VN[v] = 0 then DFSscc(v);
  // Przeglądamy listę składowych
  listp := Lscc;
  // cvn jest teraz
  // licznikiem składowych
  cvn := 0;
  while listp <> nil do
  begin
    // Zwiększamy numer składowej
    inc(cvn);
    // Wyświetlamy numer składowej
    write('SCC', cvn:3, ' :');
    // Przeglądamy listę wierzchołków
    p := listp^.v;
    while p <> nil do
    begin
      // Wyświetlamy wierzchołek składowej
      write(p^.v:3);
      // Następny wierzchołek na liście
      p := p^.next;
    end;
    writeln;
    // Następna składowa na liście
    listp := listp^.next;
  end;
  // Usuwamy zmienne dynamiczne
  for i := 0 to n-1 do
  begin
    p := graf[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;
  end;
  listp := Lscc;
  while listp <> nil do
  begin
    p := listp^.v;
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
    listr := listp;
    listp := listp^.next;
    dispose(listr);
  end;
  SetLength(graf, 0);
  SetLength(VN, 0);
  SetLength(VLow, 0);
  SetLength(VS, 0);
  S.destroy;
end.

// Wyznaczanie silnie
// spójnych składowych
// Algorytm Tarjana
// Data: 2.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych
struct SLel
{
  SLel * next;
  int v;
};

// Typ danych dla listy
// silnie spójnych składowych
struct sSLel
{
  sSLel * next;
  SLel  * v;
};

class Stack
{
  private:
    // lista przechowująca stos
    SLel * S;

  public:
    Stack(); // konstruktor
    ~Stack(); // destruktor
    bool empty(void);
    int  top(void);
    void push(int v);
    void pop(void);
};

// Zmienne globalne
//-----------------
int n, m, cvn, *VN, *VLow;
bool *VS;
Stack S;
SLel **graf;
sSLel *Lscc;

//---------------------
// Metody obiektu Stack
//---------------------

// Konstruktor
//------------
Stack::Stack()
{
  S = nullptr;
}

// Destruktor
//-----------
Stack::~Stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool Stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int Stack::top(void)
{
  if(S)
    return S->v;
  else
    return -1;
}

// Zapisuje na stos
//-----------------
void Stack::push(int v)
{
  SLel * e = new SLel;
  e->v = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void Stack::pop(void)
{
  if(S)
  {
    SLel * e = S;
    S = S->next;
    delete e;
  }
}

// Procedura wykonująca
// przejście DFS i wyznaczająca
// silnie spójną składową.
// v - wierzchołek startowy dla DFS
//---------------------------------
void DFSscc(int v)
{
  int u;
  SLel *sccp, *p;
  sSLel *listp;

  // Numerujemy wierzchołek
  // i ustawiamy wstępnie
  // parametr Low
  VN[v] = VLow[v] = ++cvn;
  // Wierzchołek na stos
  S.push(v);
  // Zapamiętujemy,
  // że v jest na stosie
  VS[v] = true;

  // Przeglądamy listę sąsiadów
  for(p = graf[v];p;p = p->next)
    // Jeśli sąsiad jest
    // nieodwiedzony, to
    if(!VN[p->v])
    {
      // wywołujemy dla niego
      // rekurencyjnie DFS
      DFSscc(p->v);
      // i obliczamy parametr Low dla v
      VLow[v] = min(VLow[v],VLow[p->v]);
    }
    // Jeśli sąsiad odwiedzony,
    // lecz wciąż na stosie,
    else if(VS[p->v])
      // to wyznaczamy parametr Low dla v
      VLow[v] = min(VLow[v],VN[p->v]);
  // Sprawdzamy,
  // czy mamy kompletną składową
  if(VLow[v] == VN[v])
  {
    // Dodajemy tę składową
    // do listy składowych
    sccp = nullptr;
    do
    {
      // Pobieramy wierzchołek ze stosu
      u = S.top();
      // Pobrany wierzchołek
      // usuwamy ze stosu
      S.pop();
      // Zapamiętujemy,
      // że nie ma go już na stosie
      VS[u] = false;
      // Nowy element listy wierzchołków
      p = new SLel;
      // Zapisujemy w nim wierzchołek
      p->v = u;
      // dodajemy go na początek listy
      p->next = sccp;
      sccp = p;
    // Kontynuujemy aż
    // do korzenia składowej
    } while(u != v);
    // Nowy element listy składowych
    listp = new sSLel;
    // Zapisujemy w nim listę
    listp->v = sccp;
    // i dołączamy na początek
    // listy składowych
    listp->next = Lscc;
    Lscc = listp;
  }
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  int i, v, u;
  SLel *p, *r;
  sSLel *listp, *listr;

  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablice dynamiczne
  graf = new SLel * [n];
  VN   = new int [n];
  VLow = new int [n];
  VS   = new bool [n];
  // Inicjujemy tablice
  for(i = 0; i < n; i++)
  {
    graf[i] = nullptr;
    VN[i]   = 0;
    VS[i]   = false;
  }
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołki tworzące krawędź
    cin >> v >> u;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako u
    p->v = u;
    // i dodajemy na początek
    // listy graf[v]
    p->next = graf[v];
    graf[v] = p;
  }
  cout << endl;
  // Wyznaczamy silnie
  // spójne składowe
  //------------------
  // Zerujemy numer wierzchołka
  cvn = 0;
  // Tworzymy pustą
  // listę składowych
  Lscc = NULL;
  // Przeglądamy kolejne wierzchołki
  for(v = 0; v < n; v++)
    // W wierzchołku nieodwiedzonym
    // uruchamiamy DFS
    if(!VN[v]) DFSscc(v);
  // cvn jest teraz
  // licznikiem składowych
  cvn = 0;
  // Przeglądamy listę składowych
  for(listp = Lscc; listp; listp = listp->next)
  {
    // Wyświetlamy numer składowej
    cout << "SCC" << setw(3)
         << ++cvn << ":";
    // Przeglądamy listę wierzchołków
    for(p = listp->v; p; p = p->next)
      // Wyświetlamy wierzchołek składowej
      cout << setw(3) << p->v;
    cout << endl;
  }
  // Usuwamy zmienne dynamiczne
  for(i = 0; i < n; i++)
  {
    p = graf[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  listp = Lscc;
  while(listp)
  {
    p = listp->v;
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
    listr = listp;
    listp = listp->next;
    delete listr;
  }
  delete [] graf;
  delete [] VN;
  delete [] VLow;
  delete [] VS;
  return 0;
}

' Wyznaczanie silnie
' spójnych składowych
' Algorytm Tarjana
' Data: 2.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy danych
Type SLel
  next As SLel Ptr
  v As Integer
End Type

Type sSLel
  next As sSLel Ptr
  v As SLel Ptr
End Type

Type Stack
  Private:
    ' lista zawierająca stos
    S As SLel Ptr
  Public:
    Declare Constructor
    Declare Destructor
    Declare Function empty As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop
End Type

' Zmienne globalne
'-----------------

Dim Shared As Integer n, m, cvn
Dim Shared As Integer Ptr VN, VLow
Dim Shared As Byte Ptr VS
Dim Shared As Stack S
Dim Shared As SLel Ptr Ptr graf
Dim Shared As sSLel Ptr Lscc

'---------------------
' Metody obiektu Stack
'---------------------

' Konstruktor
'------------
Constructor Stack
  S = 0
End Constructor

' Destruktor
'-----------
Destructor Stack
  While S
  	 pop
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function Stack.empty As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function Stack.top As Integer
  If S = 0 Then
    top = -1
  Else
    top = S->v
  End If
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push(ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v    = v
  e->next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop
  Dim e As SLel Ptr
  If S Then
  	 e = S
  	 S = S->next
  	 Delete e
  End If
End Sub

' Funkcja zwraca mniejszą z liczb a i b
'--------------------------------------
Function min(ByVal a As Integer, _
             ByVal b As Integer) _
                     As Integer
  If a < b Then
	Return a
  Else
	Return b
  EndIf
End Function

' Procedura wykonująca przejście DFS
' i wyznaczająca silnie spójną składową
' v - wierzchołek startowy dla DFS
'--------------------------------------
Sub DFSscc(ByVal v As Integer)
  Dim As Integer u
  Dim As SLel Ptr sccp, p
  Dim As sSLel Ptr listp

  ' Zwiększamy bieżący
  ' numer wierzchołka
  cvn += 1
  ' Numerujemy wierzchołek
  VN[v] = cvn
  ' i ustawiamy wstępnie parametr Low
  VLow[v] = cvn
  ' Wierzchołek na stos
  S.push(v)
  ' Zapamiętujemy, że v jest na stosie
  VS[v] = 1
  p = graf[v]
  ' Przeglądamy listę sąsiadów
  While p
    ' Jeśli sąsiad jest
    ' nieodwiedzony, to
    If VN[p->v] = 0 Then
      ' wywołujemy dla niego
      ' rekurencyjnie DFS
      DFSscc(p->v)
      ' i obliczamy parametr Low dla v
      VLow[v] = min(VLow[v],VLow[p->v])
    ' Jeśli sąsiad odwiedzony,
    ' lecz wciąż na stosie, 
    ElseIf VS[p->v] = 1 Then
      ' to wyznaczamy parametr
      ' Low dla v
      VLow[v] = min(VLow[v],VN[p->v])
    End If
    p = p->Next
  Wend
   ' Sprawdzamy,
   ' czy mamy kompletną składową
   If VLow[v] = VN[v] Then
    ' Dodajemy tę składową
    ' do listy składowych
    sccp = 0
    Do
      ' Pobieramy wierzchołek ze stosu
      u = S.top
      ' Pobrany wierzchołek
      ' usuwamy ze stosu
      S.pop
      ' Zapamiętujemy,
      ' że nie ma go już na stosie
      VS[u] = 0
      ' Nowy element listy wierzchołków
      p = new SLel
      ' Zapisujemy w nim wierzchołek
      p->v = u
      ' dodajemy go na początek listy
      p->next = sccp
      sccp = p
    ' Kontynuujemy aż do
    ' korzenia składowej
    Loop While u <> v
    ' Nowy element listy składowych
    listp = new sSLel
    ' Zapisujemy w nim listę
    listp->v = sccp
    ' i dołączamy na początek
    ' listy składowych
    listp->next = Lscc
    Lscc = listp
  End If
End Sub

' **********************
' *** Program główny ***
' **********************

Dim As Integer i, v, u
Dim As SLel Ptr p, r
Dim As sSLel Ptr listp, listr

Open Cons For Input As #1
' Odczytujemy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
graf = New SLel Ptr [n]
VN   = New Integer [n]
VLow = New Integer [n]
VS   = New Byte [n]
' Inicjujemy tablice
For i = 0 To n-1
  graf[i] = 0
  VN[i]   = 0
  VS[i]   = 0
Next
' Odczytujemy kolejne
' definicje krawędzi
For i = 1 To m
  ' Wierzchołki tworzące krawędź
  Input #1, v, u
  ' Tworzymy nowy element
  p = New SLel
  ' Numerujemy go jako u
  p->v = u
  ' Dodajemy go na początek
  ' listy graf[v]
  p->next = graf[v]
  graf[v] = p
Next
Close #1
Print
' Wyznaczamy silnie spójne składowe
'----------------------------------
' Zerujemy numer wierzchołka
cvn = 0
' Tworzymy pustą listę składowych
Lscc = 0
' Przeglądamy kolejne wierzchołki
For v = 0 To n-1
  ' W wierzchołku nieodwiedzonym
  ' uruchamiamy DFS
  If VN[v] = 0 Then DFSscc(v)
Next
' cvn jest teraz licznikiem składowych
cvn = 0
listp = Lscc
' Przeglądamy listę składowych
While listp
  cvn += 1
  ' Wyświetlamy numer składowej
  Print Using "SCC### :";cvn;
  p = listp->v
  ' Przeglądamy listę wierzchołków
  While p
    ' Wyświetlamy wierzchołek składowej
    Print Using "###";p->v;
    ' Następny wierzchołek
    p = p->next
  Wend 
  Print
  ' Następna składowa
  listp = listp->next
Wend
' Usuwamy tablice dynamiczne
'---------------------------
For i = 0 To n-1
  p = graf[i]
  While p
    r = p
    p = p->next
    Delete r
  Wend
Next
listp = Lscc
While listp
  p = listp->v
  While p
    r = p
    p = p->next
    Delete r
  Wend
  listr = listp
  listp = listp->next
  Delete listr
Wend
Delete [] graf
Delete [] VN
Delete [] VLow
Delete [] VS
End

# Wyznaczanie silnie
# spójnych składowych
# Algorytm Tarjana
# Data: 5.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasy
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


class SSLel:
    def __init__(self):
        self.next = None
        self.v = None


class Stack:
    # Konstruktor
    def __init__(self):
        self.s = None


    # Destruktor
    def __del__(self):
        while self.s:
            self.pop()


    # Sprawdza, czy stos jest pusty
    def empty(self):
        return not self.s


    # Zwraca szczyt stosu.
    def top(self):
        if not self.s:
            return -1
        else:
            return self.s.v


    # Zapisuje na stos
    def push(self, v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# Procedura wykonująca przejście DFS
# i wyznaczająca silnie spójną składową
# v - wierzchołek startowy dla DFS
def dfs_scc(v):
    global cvn, vn, vs, graf, vlow, s
    global lscc
    # Zwiększamy bieżący
    # numer wierzchołka
    cvn += 1
    # Numerujemy wierzchołek
    vn[v] = cvn
    # i ustawiamy wstępnie parametr Low
    vlow[v] = cvn
    # Wierzchołek na stos
    s.push(v)
    # Zapamiętujemy, że v jest na stosie
    vs[v] = True
    p = graf[v]
    # Przeglądamy listę sąsiadów
    while p:
        # Jeśli sąsiad jest
        # nieodwiedzony, to
        if not vn[p.v]:
            # wywołujemy dla niego
            # rekurencyjnie DFS
            dfs_scc(p.v)
            # i obliczamy parametr Low dla v
            vlow[v] = min(vlow[v],vlow[p.v])
        # Jeśli sąsiad odwiedzony,
        # lecz wciąż na stosie, 
        elif vs[p.v]:
            # to wyznaczamy parametr
            # Low dla v
            vlow[v] = min(vlow[v],vn[p.v])
        p = p.next
    # Sprawdzamy,
    # czy mamy kompletną składową
    if vlow[v] == vn[v]:
        # Dodajemy tę składową
        # do listy składowych
        sccp = None
        while True:
            # Pobieramy wierzchołek
            # ze stosu
            u = s.top()
            # Pobrany wierzchołek
            # usuwamy ze stosu
            s.pop()
            # Zapamiętujemy,
            # że nie ma go już na stosie
            vs[u] = False
            # Nowy element
            # listy wierzchołków
            p = SLel()
            # Zapisujemy w nim wierzchołek
            p.v = u
            # dodajemy go na początek listy
            p.next = sccp
            sccp = p
            # Kontynuujemy aż do
            # korzenia składowej
            if u == v: break
        # Nowy element listy składowych
        listp = SSLel()
        # Zapisujemy w nim listę
        listp.v = sccp
        # i dołączamy na początek
        # listy składowych
        listp.next = lscc
        lscc = listp

# **********************
# *** Program główny ***
# **********************

s = Stack()
# Odczytujemy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
graf = [None] * n
vn = [0] * n
vlow = [0] * n
vs = [False] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołki tworzące krawędź
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako u
    p.v = u
    # Dodajemy go na początek
    # listy graf[v]
    p.next = graf[v]
    graf[v] = p
print()
# Wyznaczamy silnie spójne składowe
#----------------------------------
# Zerujemy numer wierzchołka
cvn = 0
# Tworzymy pustą listę składowych
lscc = None
# Przeglądamy kolejne wierzchołki
for v in range(n):
    # W wierzchołku nieodwiedzonym
    # uruchamiamy DFS
    if not vn[v]: dfs_scc(v)
# cvn jest teraz licznikiem składowych
cvn = 0
listp = lscc
# Przeglądamy listę składowych
while listp:
    cvn += 1
    # Wyświetlamy numer składowej
    print("SCC%3d :" % cvn, end="")
    p = listp.v
    # Przeglądamy listę wierzchołków
    while p:
        # Wyświetlamy wierzchołek składowej
        print("%3d" % p.v, end="")
        # Następny wierzchołek
        p = p.next
    print()
    # Następna składowa
    listp = listp.next
# Usuwamy tablice dynamiczne
#---------------------------
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
listp = lscc
while listp:
    while listp.v:
        listp.v = listp.v.next
    listp = listp.next
del graf, vn, vlow, vs