// BFS-macierz sąsiedztwa
// Data: 23.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bfs_adj;

// Typy dla dynamicznej
// macierzy i kolejki
type
  // Wiersz
  nptr = array of byte;
  // Cała macierz
  mptr = array of nptr;

  PSLel = ^SLel;
  SLel = record
    next  : PSLel;
    Data: integer;
  end;

// Zmienne globalne
var
  // Liczba wierzchołków
  n : integer;
  // Macierz sąsiedztwa
  A : mptr;
  // Tablica odwiedzin
  vs : array of boolean;

// Procedura przejścia wszerz
//---------------------------
procedure BFS(v : integer);
var
  i : integer;
  // Kolejka
  q, head, tail : PSLel;
begin
  // W kolejce umieszczamy v
  new(q);
  q^.next := nil;
  q^.Data:= v;
  head := q; tail := q;
  // Wierzchołek v oznaczamy
  // jako odwiedzony
  vs[v] := true;
  while head <> nil do
  begin
    // Odczytujemy v z kolejki
    v := head^.data;
    // Usuwamy z kolejki odczytane v
    q := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(q);
    write(v:3);
    for i := 0 to n-1 do
      if (A[v][i] = 1) and
         (vs [i] = false) then
      begin
        // W kolejce umieszczamy
        // nieodwiedzonych sąsiadów
        new(q);
        q^.next := nil;
        q^.Data:= i;
        if tail = nil then head := q
        else tail^.next := q;
        tail := q;
        // i oznaczamy ich
        // jako odwiedzonych
        vs[i] := true;
      end;
  end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  m, i, j, v1, v2 : integer;

begin
  // Czytamy liczbę wierzchołków
  // i krawędzi
  read(n, m);
  // Tworzymy tablicę wskaźników
  SetLength(A, n);
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  for i := 0 to n-1 do
    // Tworzymy wiersze
    SetLength(A[i], n);
  // Macierz wypełniamy zerami
  for i := 0 to n-1 do
  begin
    // Zerujemy tablicę odwiedzin
    vs[i] := false;
    for j := 0 to n-1 do
      A[i][j] := 0;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 1 to m do
  begin
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Krawędź v1->v2 obecna
    A[v1][v2] := 1;
  end;
  writeln;
  // Przechodzimy graf wszerz
  BFS(0);
  // Usuwamy macierz
  for i := 0 to n-1 do
    SetLength(A[i], 0);
  SetLength(A, 0);
  SetLength(vs, 0);
  writeln;
end.

// BFS-macierz sąsiedztwa
// Data: 23.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typ elementów listy dla kolejki
struct SLel
{
  SLel * next;
  int data;
};

// Zmienne globalne

// Liczba wierzchołków
int n;
// Macierz sąsiedztwa
char ** A;
// Tablica odwiedzin
bool * vs;

// Procedura przejścia wszerz
//---------------------------
void BFS(int v)
{
  int i;
  // Kolejka
  SLel *q, *head, *tail;

  // W kolejce umieszczamy v
  q = new SLel;
  q->next = NULL;
  q->data = v;
  head = tail = q;
  // Wierzchołek v oznaczamy
  // jako odwiedzony
  vs[v] = true;
  while(head)
  {
    // Odczytujemy v z kolejki
    v = head->data;
    // Usuwamy z kolejki odczytane v
    q = head;
    head = head->next;
    if(!head) tail = NULL;
    delete q;
    cout << setw(3) << v;
    for(i = 0; i < n; i++)
      if((A[v][i] == 1) &&
         !vs[i])
      {
        // W kolejce umieszczamy
        // nieodwiedzonych sąsiadów
        q = new SLel;
        q->next = NULL;
        q->data = i;
        if(!tail) head = q;
        else tail->next = q;
        tail = q;
        // i oznaczamy ich
        // jako odwiedzonych
        vs[i] = true;
      }
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int m, i, j, v1, v2;

  // Czytamy liczbę wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę wskaźników
  A = new char * [n];
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  for(i = 0; i < n; i++)
    // Tworzymy wiersze
    A[i] = new char [n];
  // Macierz wypełniamy zerami
  for(i = 0; i < n; i++)
  {
    // Zerujemy tablicę odwiedzin
    vs[i] = false;
    for(j = 0; j < n; j++)
      A[i][j] = 0;
  }
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Krawędź v1->v2 obecna
    A[v1][v2] = 1;
  }
  cout << endl;
  // Przechodzimy graf wszerz
  BFS(0);
  // Usuwamy macierz
  for(i = 0; i < n; i++)
    delete A[i];
  delete [] A;
  delete [] vs;
  cout << endl;
  return 0;
}

' BFS-macierz sąsiedztwa
' Data: 23.07.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typ elementów listy dla kolejki
Type SLel
  next As SLel Ptr
  data As Integer
End Type

' Zmienne globalne

' Liczba wierzchołków
Dim Shared As Integer n
' Macierz sąsiedztwa
Dim Shared As Byte Ptr Ptr A
' Tablica odwiedzin
Dim Shared As Byte Ptr vs

' Procedura przejścia wszerz
'---------------------------
Sub BFS(ByVal v As Integer)

  Dim As Integer i
  ' Kolejka
  Dim As SLel Ptr q, head, tail

' W kolejce umieszczamy v
  q = new SLel
  q->next = 0
  q->data = v
  head = q: tail = q
  ' Wierzchołek v oznaczamy
  ' jako odwiedzony
  vs[v] = 1
  While head
    ' Odczytujemy v z kolejki
    v = head->Data
    ' Usuwamy z kolejki
    ' odczytane v
    q = head
    head = head->Next
    If head = 0 Then tail = 0
    delete q
    Print Using "###";v;
    For i = 0 To n-1
      if (A[v][i] = 1) AndAlso _
         (vs[i] = 0) Then
        ' W kolejce umieszczamy
        ' nieodwiedzonych sąsiadów
        q = new SLel
        q->next = 0
        q->data = i
        If tail = 0 Then
          head = q
        Else
          tail->next = q
        End If
        tail = q
        ' i oznaczamy ich
        ' jako odwiedzonych
        vs[i] = 1
      End If
    Next
  Wend
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer m, i, j, v1, v2

Open Cons For Input As #1
' Czytamy liczbę wierzchołków
' i krawędzi
Input #1, n, m

' Tworzymy tablicę wskaźników
A = New Byte Ptr [n]
' Tworzymy tablicę odwiedzin
vs = New Byte [n]
For i = 0 To n-1
  ' Tworzymy wiersze
  A[i] = New Byte [n]
Next
' Macierz wypełniamy zerami
For i = 0 To n-1
  ' Zerujemy tablicę odwiedzin
  vs[i] = 0
  For j = 0 To n-1
    A[i][j] = 0
  Next
Next
' Odczytujemy kolejne
definicje krawędzi
For i = 1 To m
  ' Wierzchołek startowy
  ' i końcowy krawędzi
  Input #1, v1, v2
  ' Krawędź v1->v2 obecna
  A[v1][v2] = 1
Next
Close #1
Print
' Przechodzimy graf wszerz
BFS (0)
' Usuwamy macierz
For i = 0 To n-1
  Delete A[i]
Next
Delete [] A
Delete [] vs
Print
End

# BFS-macierz sąsiedztwa
# Data: 8.12.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# Klasa elementów listy dla kolejki
class SLel:
    def __ini__(self):
        self.next = None
        self.data = 0


# Procedura przejścia wszerz
#---------------------------
def bfs(a,vt,n,v):
    # Kolejka
    head = None
    tail = None
    # W kolejce umieszczamy v
    q = SLel()
    q.next = None
    q.data = v
    head = q
    tail = q
    # Wierzchołek v oznaczamy jako odwiedzony
    vt[v] = True
    while head:
        # Odczytujemy v z kolejki
        v = head.data
        # Usuwamy z kolejki odczytane v
        q = head
        head = head.next
        if not head: tail = None
        del q
        print("%3d" % v, end="")
        for i in range(n):
            if (a[v][i] == 1) and \
               not vs[i]:
               # W kolejce umieszczamy
               # nieodwiedzonych sąsiadów
               q = SLel()
               q.next = None
               q.data = i
               if not tail:
                   head = q
               else:
                   tail.next = q
               tail = q
               # i oznaczamy ich jako odwiedzonych
               vt[i] = True


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę wskaźników
a = []
# Tworzymy tablicę odwiedzin
vs = [False] * n
for i in range(n):
    # Tworzymy wiersze
    x = [0] * n
    a.append(x)
# Odczytujemy kolejne definicje krawędzi
for i in range(m):
    # Wierzchołek startowy i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Krawędź v1.v2 obecna
    a[v1][v2] = 1
print()
# Przechodzimy graf wszerz
bfs(a,vs,n,0)
# Usuwamy macierz
for i in range(n):
    a[i] = None
del a, vs
print()

// BFS-listy sąsiedztwa
// Data: 23.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bfs_adjl;

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

  TList = array of PSLel;

// Zmienne globalne
var
  // Liczba wierzchołków i krawędzi
  n : integer;
  // Tablica list sąsiedztwa
  A : TList;
  // Tablica odwiedzin
  vs : array of boolean;

// Procedura przejścia wszerz
//---------------------------
procedure BFS(v : integer);
var
  // Kolejka
  p, q, head, tail : PSLel;
begin
  // W kolejce umieszczamy v
  new(q);
  q^.next := nil;
  q^.v := v;
  head := q; tail := q;
  // Wierzchołek v oznaczamy
  // jako odwiedzony
  vs[v] := true;
  while head <> nil do
  begin
    // Odczytujemy v z kolejki
    v := head^.v;
    // Usuwamy z kolejki odczytane v
    q := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(q);
    write(v:3);
    p := A[v];
    while p <> nil do
    begin
      if vs[p^.v] = false then
      begin
        // W kolejce umieszczamy
        // nieodwiedzonych sąsiadów
        new(q);
        q^.next := nil;
        q^.v := p^.v;
        if tail = nil then head := q
        else tail^.next := q;
        tail := q;
        // i oznaczamy ich jako odwiedzonych
        vs[p^.v] := true;
      end;
      p := p^.next;
    end;
   end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  m, i, v1, v2 : integer;
  p, r : PSLel;

begin
  // Czytamy liczbę wierzchołków
  // i krawędzi
  read(n, m);
  // Tworzymy tablicę
  // list sąsiedztwa
  SetLength(A, n);
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  // Tablice wypełniamy
  // pustymi listami
  for i := 0 to n-1 do
  begin
    A[i] := nil;
    vs[i] := false;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 0 to m-1 do
  begin
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako v2
    p^.v := v2;
    // Dodajemy go na początek
    // listy A[v1]
    p^.next := A[v1];
    A[v1] := p;
  end;
  writeln;
  // Przechodzimy graf wszerz
  BFS(0);
  // Usuwamy tablicę list sąsiedztwa
  for i := 0 to n-1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;
  SetLength(A, 0);
  SetLength(vs, 0);
  writeln;
end.

// BFS-listy sąsiedztwa
// Data: 23.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

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

// Zmienne globalne

// Liczba wierzchołków
int n;
// Macierz sąsiedztwa
SLel ** A;
// Tablica odwiedzin
bool * vs;

// Procedura przejścia wszerz
//---------------------------
void BFS(int v)
{
  // Kolejka
  SLel *p, *q, *head, *tail;

  // W kolejce umieszczamy v
  q = new SLel;
  q->next = NULL;
  q->v = v;
  head = tail = q;

  // Wierzchołek v oznaczamy
  // jako odwiedzony
  vs[v] = true;
  while(head)
  {
    // Odczytujemy v z kolejki
    v = head->v;

    // Usuwamy z kolejki odczytane v
    q = head;
    head = head->next;
    if(!head) tail = NULL;
    delete q;
    cout << setw (3) << v;
    for(p = A[v]; p; p = p->next)
    if(!vs[p->v])
    {
      // W kolejce umieszczamy
      // nieodwiedzonych sąsiadów
      q = new SLel;
      q->next = NULL;
      q->v = p->v;
      if(!tail) head = q;
      else      tail->next = q;
      tail = q;
      // i oznaczamy ich
      // jako odwiedzonych
      vs[p->v] = true;
    }
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int m, i, v1, v2;
  SLel *p, *r;

  // Czytamy liczbę wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę list sąsiedztwa
  A = new SLel * [n];
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  // Tablicę wypełniamy pustymi listami
  for(i = 0; i < n; i++)
  {
    A[i] = NULL;
    vs[i] = false;
  }
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako v2
    p->v = v2;
    // Dodajemy go na początek
    // listy A[v1]
    p->next = A[v1];
    A[v1] = p;
  }
  cout << endl;
  // Przechodzimy graf wszerz
  BFS(0);
  // Usuwamy tablicę
  // list sąsiedztwa
  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  delete [] vs;
  cout << endl;
  return 0;
}

' BFS-listy sąsiedztwa
' Data: 23.07.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

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

' Zmienne globalne

' Liczba wierzchołków
Dim Shared As Integer n
' Tablica list sąsiedztwa
Dim Shared As SLel Ptr Ptr A
' Tablica odwiedzin
Dim Shared As Byte Ptr vs

' Procedura przejścia wszerz
'---------------------------
sub BFS (ByVal v As Integer)

  ' Kolejka
  Dim As SLel Ptr p, q, head, tail

  ' W kolejce umieszczamy v
  q = new SLel
  q->next = 0
  q->v = v
  head = q: tail = q
  ' Wierzchołek v oznaczamy jako odwiedzony
  vs[v] = 1
  While head
    ' Odczytujemy v z kolejki
    v = head->v
    ' Usuwamy z kolejki odczytane v
    q = head
    head = head->Next
    If head = 0 Then tail = 0
    delete q
    Print Using "###";v;
    p = A[v]
    while p <> 0
      If vs[p->v] = 0 Then
        ' W kolejce umieszczamy
        ' nieodwiedzonych sąsiadów
        q = new SLel
        q->next = 0
        q->v = p->v
        If tail = 0 Then
          head = q
        Else
          tail->next = q
        End If
        tail = q
        ' Wierzchołek v oznaczamy
        ' jako odwiedzony
        vs[p->v] = 1
      End If
      p = p->Next
    Wend 
  Wend
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer m, i, v1, v2
Dim As SLel Ptr p, r

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę list sąsiedztwa
A = new SLel Ptr [n]
' Tworzymy tablicę odwiedzin
vs = New Byte [n]
' Tablicę wypełniamy pustymi listami
For i = 0 To n-1
  A[i] = 0
  vs[i] = 0
Next
' Odczytujemy kolejne definicje krawędzi
For i = 0 To m -1
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2 
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako v2
  p->v = v2
  ' Dodajemy go na początek listy A[v1]
  p->next = A[v1]
  A[v1] = p
Next
Close #1
Print
' Przechodzimy graf wszerz
BFS(0)
' Usuwamy tablicę list sąsiedztwa
For i = 0 To n-1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [] A
Delete [] vs
Print
End

# BFS-listy sąsiedztwa
# Data: 10.12.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

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


# Procedura przejścia wszerz
#---------------------------
def bfs(a,vt,n,v):
    # W kolejce umieszczamy v
    q = SLel()
    q.v = v
    head = q
    tail = q
    # Wierzchołek v oznaczamy jako odwiedzony
    vt[v] = True
    while head:
        # Odczytujemy v z kolejki
        v = head.v
        # Usuwamy z kolejki odczytane v
        q = head
        head = head.next
        if not head: tail = None
        del q
        print("%3d" % v, end="")
        p = a[v]
        while p:
            if not vt[p.v]:
                # W kolejce umieszczamy
                # nieodwiedzonych sąsiadów
                q = SLel()
                q.v = p.v
                if not tail:
                    head = q
                else:
                    tail.next = q
                tail = q
                # Wierzchołek v oznaczamy
                # jako odwiedzony
                vt[p.v] = True
            p = p.next


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę odwiedzin
vs = [False] * n
# Tworzymy tablicę list sąsiedztwa
a = [None] * n
# Odczytujemy kolejne definicje krawędzi
for i in range(m):
    # Wierzchołek startowy i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako v2
    p.v = v2
    # Dodajemy go na początek listy A[v1]
    p.next = a[v1]
    a[v1] = p
print()
# Przechodzimy graf wszerz
bfs(a,vs,n,0)
# Usuwamy tablicę list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a, vs
print()