// Arup Guha
// 9/21/2023
// Solution to Fall 2023 COP 3502 Program 3B: Where to Sit?
// Outputs first lexicographical valid seating arrangement.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXNAMES 10
#define MAXLEN 20

// Make global for ease of use.
int numNames;
char names[MAXNAMES][MAXLEN];
int popcorn[MAXNAMES];

// Will store who can sit next to whom.
int cansit[MAXNAMES][MAXNAMES];

int lookup(char* name);
int go(int* perm, int* used, int k);
int isvalid(int* perm);
int okpopcorn(int* perm);
int okorder(int* perm);
void print(int* perm);

int main() {

    int numBad;
    scanf("%d%d", &numNames, &numBad);

    // Read names, popcorn info.
    for (int i=0; i<numNames; i++)
        scanf("%s%d", names[i], &popcorn[i]);

    for (int i=0; i<numNames; i++)
        for (int j=0; j<numNames; j++)
            cansit[i][j] = 1;

    // Read bad pairs.
    for (int i=0; i<numBad; i++) {
        char name1[MAXLEN], name2[MAXLEN];
        scanf("%s%s", name1, name2);
        int idx1 = lookup(name1);
        int idx2 = lookup(name2);
        cansit[idx1][idx2] = 0;
        cansit[idx2][idx1] = 0;
    }

    // Set up permutation and used array.
    int perm[MAXNAMES];
    int used[MAXNAMES];
    for (int i=0; i<numNames; i++)
        used[i] = 0;

    // Solve it...
    int res = go(perm, used, 0);

    // Print it.
    print(perm);

    return 0;
}

// Returns the location in the list this particular name is.
int lookup(char* name) {

    // Just go in order and find the name.
    for (int i=0; i<numNames; i++)
        if (strcmp(name, names[i]) == 0)
            return i;

    // Should never get here.
    return -1;
}

int go(int* perm, int* used, int k) {

    // Base case.
    if (k == numNames)
        return isvalid(perm);

    // Go through each possible choice for slot k.
    for (int i=0; i<numNames; i++) {

        // Skip, it's used.
        if (used[i]) continue;

        // Put i in slot k.
        used[i] = 1;
        perm[k] = i;

        // Recurse.
        int res = go(perm, used, k+1);

        // Stop if we found a solution and return that we did.
        if (res) return 1;

        // Undo so we can put something else in slot k.
        used[i] = 0;
    }

    // No solutions...
    return 0;
}

// Returns 1 if this permutation is valid, 0 otherwise.
int isvalid(int* perm) {
    return okpopcorn(perm) && okorder(perm);
}

int okpopcorn(int* perm) {

    // Go through each person.
    for (int i=0; i<numNames; i++) {

        // ith person has popcorn, so we're good.
        if (popcorn[perm[i]]) continue;

        // Person on left has popcorn, so we're good.
        if (i>0 && popcorn[perm[i-1]]) continue;

        // Person on right has popcorn...
        if (i<numNames-1 && popcorn[perm[i+1]]) continue;

        // If we get here, person i can't get popcorn...so sad!
        return 0;
    }

    // We're good!
    return 1;
}

int okorder(int* perm) {

    // If any pair is banned, we can't do it.
    for (int i=0; i<numNames-1; i++)
        if (!cansit[perm[i]][perm[i+1]])
            return 0;

    // We're good!
    return 1;
}

// Prints the corresponding permutations of names suggested by perm
// in the format prescribed by the assignment.
void print(int* perm) {
    for (int i=0; i<numNames; i++)
        printf("%s\n", names[perm[i]]);
}