It looks like you should use CSOAA which allows multiple labels. They need to be natural numbers and less than or equal to K where K is the number of classes. Like this:
1 2 3 class1 | f1:2 f2:3
4 2 5 class2 | f3:7 f5:3
2 3 class3 | f4:2 f2:2
For more detail, see the Vowpal Wabbit documentation: https://github.com/JohnLangford/vowpal_wabbit/wiki/Cost-Sensitive-One-Against-All-%28csoaa%29-multi-class-example