#include <stdio.h>
#include <stdlib.h>
 
// Structure to represent a warrior
typedef struct {
    int x;
    int y;
} Warrior;
 
// Function to compare two elements for sorting
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}
 
// Function to count the frequency of numbers and return the sorted list of unique numbers
int countAndSortFrequencies(Warrior *warriors, int N, int *frequency, int *uniqueNumbers) {
    int maxVal = 400000;
    for (int i = 0; i < N; i++) {
        frequency[warriors[i].x]++;
        frequency[warriors[i].y]++;
    }
 
    int uniqueCount = 0;
    for (int i = 1; i <= maxVal; i++) {
        if (frequency[i] > 0) {
            uniqueNumbers[uniqueCount++] = i;
        }
    }
 
    qsort(uniqueNumbers, uniqueCount, sizeof(int), compare);
    return uniqueCount;
}
 
// Function to find the maximum number of warriors that can be selected
int maxWarriors(int N, Warrior *warriors) {
    int maxVal = 400000;
    int *frequency = (int *)calloc(maxVal + 1, sizeof(int));
    int *uniqueNumbers = (int *)malloc((maxVal + 1) * sizeof(int));
    int uniqueCount = countAndSortFrequencies(warriors, N, frequency, uniqueNumbers);
 
    int *selectedIdentifiers = (int *)calloc(maxVal + 1, sizeof(int));
    int selectedWarriorsCount = 0;
 
    for (int i = 0; i < uniqueCount; i++) {
        int number = uniqueNumbers[i];
        if (!selectedIdentifiers[number]) {
            for (int j = 0; j < N; j++) {
                if ((warriors[j].x == number || warriors[j].y == number) &&
                    !selectedIdentifiers[warriors[j].x] && !selectedIdentifiers[warriors[j].y]) {
                    selectedIdentifiers[warriors[j].x] = 1;
                    selectedIdentifiers[warriors[j].y] = 1;
                    selectedWarriorsCount++;
                    if (selectedWarriorsCount == N) {
                        free(frequency);
                        free(uniqueNumbers);
                        free(selectedIdentifiers);
                        return selectedWarriorsCount;
                    }
                }
            }
        }
    }
 
    free(frequency);
    free(uniqueNumbers);
    free(selectedIdentifiers);
    return selectedWarriorsCount;
}
 
int main() {
    int N = 20;
    Warrior warriors[] = {
        {6, 19}, {8, 20}, {16, 8}, {3, 20}, {9, 13}, {10, 11},
        {8, 15}, {20, 11}, {18, 17}, {8, 14}, {15, 16}, {20, 1},
        {5, 2}, {7, 11}, {14, 7}, {4, 11}, {14, 15}, {20, 5},
        {15, 1}, {12, 1}
    };
    printf("%d\n", maxWarriors(N, warriors));  // Output: 17
    return 0;
}