/*************************************************************************
 *                                                                       *
 *                       X Olimpiada Informatyczna                       *
 *                                                                       *
 *   Rozwiązanie zadania: Małpki                                         *
 *   Plik:                mal1.cpp                                       *
 *   Autor:               Krzysztof Onak                                 *
 *************************************************************************/

#include <iostream>
#include <vector>
using namespace std;

// ograniczenia
const int MAXN = 200000;
const int MAXM = 2 * MAXN;

// oznacza, że małpka nic nie trzyma w danej ręce
const int PUSZCZONA = -1;

// małpka na drzewie, nigdy nie spadła
const int NIGDY = -1;
// małpka leży na ziemi
const int ZIEMIA = -2;

int n, m;
int lapki[MAXN][2];  // opisuje, kogo trzymają łapki małpki
int uchwyt[MAXM][2]; // opisuje kto kogo puścił w danej chwili czasu

void wczytaj()
{
  cin >> n >> m;
  // wczytujemy stan łapek małpek
  for(int i = 0; i < n; ++i) {
    int l, p;
    cin >> l >> p;
    lapki[i][0] = l == PUSZCZONA ? l : l - 1;
    lapki[i][1] = p == PUSZCZONA ? p : p - 1;
  }
  // wczytujemy kto kogo puścił i uaktualniamy odpowiednio stan łapek
  for(int i = 0; i < m; ++i) {
    int malpa, lapka;
    cin >> malpa >> lapka;
    uchwyt[i][0] = lapki[--malpa][--lapka];
    uchwyt[i][1] = malpa;
    lapki[malpa][lapka] = PUSZCZONA;
  }
}

vector<int> krawedzie[MAXN];  // krawedzie grafu małpek
int czas[MAXN];  // czas, w którym spadła dana małpka

// startujemy od małpki v i nadajemy wszystkim małpkom, z którymi
// jest ona związana i które leżą na ziemi, czas odwiedzin t
void dfs(int v, int t)
{
  if (czas[v] != ZIEMIA) return;
  czas[v] = t;
  int sasiadow = krawedzie[v].size();
  for(int i = 0; i < sasiadow; ++i)
    dfs(krawedzie[v][i], t);
}

// przygotowujemy krawędzie grafu małpek
// i inicjalizujemy czas upadku
void przygotuj()
{
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < 2; ++j)
      if (lapki[i][j] != PUSZCZONA) {
        krawedzie[lapki[i][j]].push_back(i);
	krawedzie[i].push_back(lapki[i][j]);
      }
  for(int i = 0; i < n; ++i)
    czas[i] = ZIEMIA;
}

// obliczamy czasy upadku
void przetworz()
{
  // małpki, które w ogóle nie spadły
  dfs(0, NIGDY);
  // dodajemy kolejne uchwyty
  for(int i = m - 1; i >= 0; --i) {
    int v = uchwyt[i][0], w = uchwyt[i][1];
    // czyżby nowe małpki połączyły się z drzewem?
    if (czas[v] == ZIEMIA && czas[w] != ZIEMIA) {
      dfs(v, i);
    } else if (czas[w] == ZIEMIA && czas[v] != ZIEMIA) {
      dfs(w, i);
    }
    // nowe krawędzie w grafie
    krawedzie[v].push_back(w);
    krawedzie[w].push_back(v);
  }
}

// wypisujemy wynik
void wypisz()
{
  for(int i = 0; i < n; ++i)
    cout << czas[i] << '\n';
}

int main()
{
  wczytaj();
  przygotuj();
  przetworz();
  wypisz();
}
